Oscar Dolloway Oscar Dolloway - 5 months ago 21
Python Question

Binary Search python 3.5

I'm trying to write binary search in python 3.5 but it wont work I'm not sure why.

def binarySearch(alist, value):

first = 0
last = len(alist)-1
midpoint = (last//2)
while binarySearch:
if value == alist[midpoint]:
return True and print ("found")
else:
if value < midpoint:
last = midpoint-1
else:
if value > midpoint:
first = midpoint+1
binarySearch([1,2,3,4,5,6,7,8],3)


if I put value as 4 it displays found, if I put anything else nothing happens and its stuck running doing nothing.

Thanks for your help.

Answer Source

User1915011 beat me to my answer. In line with his answer and @wim's comment, I have made the following changes your binarySearch method.

  1. Changed the loop to use the found variable
  2. Added an additional assignment to midpoint inside the loop
  3. Ensure the loop terminates by adding first<=last
  4. Return found after the while loop to indicate success or failure.

    def binarySearch(alist, value):
    
        first = 0
        last = len(alist)-1
        found = False
        while first<=last and not found:
            midpoint = (first + last)//2
            if value == alist[midpoint]:        
                found =  True 
            else:
                if value < alist[midpoint]:
                    last = midpoint-1
                else:
                    if value > midpoint:
                        first = midpoint+1  
        return found
    
    if binarySearch([1,2,3,4,5,6,7,8],3):
        print "found"