0

I am new into python and i am trying to implement binary search via recursion , I could see the solution of internet but i tried all way myself because i wanted to learn , so this is my approach :

y=7
count=0
def hello(x):

    while len(x)>0:
        for i in x:
            a=len(x)//2

            if y<x[a]:
                print("left_most_side", a)
                return hello(x[:a])

            elif y==x[a]:
                print("middle", a)
                return a
            elif y>x[a]:
                print("right_most_side", a)
                return hello(x[a:])


        return x

hello([1,2,3,4,5,6,7])

Its working perfects and giving the output as expected but issue is , its printing the index of bi-sectioned list, while i need the index of origional list. example : a=[1,2,3,4] it bisection this and now [1,2] and [3,4] and now if i had to find 4 then it will print 4 is at position 0 , answer is correct but only in bisectioned list , while the correct answer is "4" is in origional list at position 3 so it should print 3 , that's the problem i am facing.

Improve this question
2
  • Pass the whole list, with a left, and right parameter. Commented Sep 21, 2017 at 11:25
  • @cᴏʟᴅsᴘᴇᴇᴅ if i pass whole list then how binary search will work ? Commented Sep 21, 2017 at 11:30

2 Answers 2

Reset to default
1

As mentioned in my comment, I would recommend passing the entire list, along with the upper and lower bounds to search. This will take care of the index issue.

Furthermore, please do not have your function work with global variables. It's bad practice.

def hello(x, key, l, r):
     if l < r:
        a = (l + r) // 2
        if key < x[a]:
            return hello(x, key, l, a + 1)

        elif key > x[a]:
            return hello(x, key, a + 1, r)

        else:
            return a

     else:
          return -1

In [288]: src = [1,2,3,4,5,6,7]

In [289]: hello(src, key=7, l=0, r=7) 
Out[289]: 6

In [290]: hello(src, key=0, l=0, r=7) 
Out[290]: -1

In [291]: hello(src, key=1, l=0, r=7) 
Out[291]: 0
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Use left and right to track the array bounds as it passes through recursion like this

y=7

def hello (x, left, right, query):
    if right >= left:
        mid = left + (right - left)/2
        if x[mid] == query:
            return mid
        elif x[mid] > query:
            return hello(x, left, mid-1, query)
        else:
            return hello(x, mid+1, right, query)
    else:
        # we found nothing
        return -1
arr = [1,2,3,4,5,6,7]

print hello(arr,0,len(arr),y)
Improve this answer

2 Comments

This is shockingly similar to my answer. That puts me off.
These are standard algorithms after all :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.