CODEWITHSUNDEEP
algorithmpython-3.xbinary-search
Souvik Ray
Souvik Ray

Reputation: 3018

Binary search program doesn't work as expected.What's wrong?

I am getting value as "None" in my program?Where have I gone wrong?

lis2 = [1, 3, 6, 2, 5, 4, 8, 12]
lis2 = sorted(lis2)
start = 0
end = len(lis2)
mid = (start+end)/2

def binary_search(i):
    global mid,start,end
    if i==lis2[mid]:
        return "Found"
    elif i<lis2[mid]:
        end = mid-1
        mid = (start+end)/2
    elif i>lis2[mid]:
        start = mid+1
        mid = (start+end)/2
    else:
        return "Not Found"

    binary_search(i)


print(binary_search(6))

Any help is appreciated.Thanks in advance!

Upvotes: 0

Views: 65

Answers (2)

GAURANG VYAS
GAURANG VYAS

Reputation: 689

Three mistakes are present -

  • First as mentioned in the comment and one of the answer you wrote - binary_search(i) instead of return binary_search(i)
  • Second is logical error. Your code will run into infinite loop if the elements is not present in the list. To avoid this check if start > end, if ti happens then element is not present.
  • Third you initialised end to len(lis2) , this will give IndexError: list index out of range if you are trying to search for an element which is not present in the list and is greater than the max element in the list ( say 23 ). So change end = len(lis2) to end = len(lis2)-1

Correct Code - 

lis2 = [1, 3, 6, 2, 5, 4, 8, 12]
lis2 = sorted(lis2)
start = 0
end = len(lis2)-1
mid = int((start+end)/2)

def binary_search(i):
     global mid,start,end
     if(start>end):
        return "Not Found"
     if i==lis2[mid]:
        return "Found"
     elif i<lis2[mid]:
        end = mid-1
        mid = int((start+end)/2)
     elif i>lis2[mid]:
         start = mid+1
         mid = int((start+end)/2)
     return binary_search(i)

print(binary_search(6))

Upvotes: 1

d9ngle
d9ngle

Reputation: 1469

at the end of your function, you need to return the result when calling the function recursivley : 

def binary_search(i):
global mid,start,end
if i==lis2[mid]:
    return "Found"
elif i<lis2[mid]:
    end = mid-1
    mid = (start+end)/2
elif i>lis2[mid]:
    start = mid+1
    mid = (start+end)/2
else:
    return "Not Found"

return binary_search(i) # <----- EDITED

Upvotes: 0

Related Questions