I am trying to implement binary search with the following function:
def buggy_binary_search(input, key):
low = 0
high = len(input)-1
mid = (low + high)/2
while low <= high:
if input[mid] == key:
return mid
if input[mid] > key:
high = mid - 1
else:
low = mid
return -1
The above function when run, gets into a infinite loop. How can I correct that?
Since, you are not updating the value of mid the while loop keeps on checking the same element and runs into an infinite loop, to correct that as many people have pointed out, update mid in the while loop.
Also, you should do low = mid+1 and not low = mid.
The full code is given below:-
def binary_search(input, key):
low = 0
high = len(input)-1
mid = (low + high)/2
while low <= high:
mid = (low + high)/2
if input[mid] == key:
return mid
if input[mid] > key:
high = mid - 1
else:
low = mid + 1
return -1
Make sure the input is sorted!
high == sys.maxint?def binary_search(input, key):
low = 0
high = len(input)-1
mid = (low + high)/2
while low <= high:
mid = (low + high)/2
if input[mid] == key:
return mid
if input[mid] > key:
high = mid - 1
else:
low = mid + 1
return -1
as Dmitry Bychenko said, you should put mid = (low + high)/2 in the loop.
input sorted in ascending or descending order.
input[mid], the range should be adjusted so low = mid + 1, shouldn't it?low = mid+1 is correct, should be adjusted."""don't use "input" as a variable name. its a python keyword.
make sure your array is sorted
use integer division when computing midpoint
"""
def bsearch(input_array,target):
lo,hi=0,len(input_array)-1
while lo<=hi:
mid=(lo+hi)//2
if input_array[mid]==target:
print "found at ",mid
return mid
if input_array[mid]>target:
print "look left"
hi=mid-1
if input_array[mid]<target:
print "look right"
lo=mid+1
return -1
a=[2,4,7,8,12,88,99,101]
target=7
assert bsearch(a,1134)==-1,"value 1134 isn't in array but says it is"
assert bsearch(a,2)==0,"value 2 is in the zero element of array.begenning"
assert bsearch(a,101)==7,"value 101 is in the 7th element of array. end"
assert bsearch(a,12)==4,"value 12 is in the 4th element of array. midpoint"
