I am trying to perform a binary search on a list in python. List is created using command line arguments. User inputs the number he wants to look for in the array and he is returned the index of the element. For some reason, the program only outputs 1 and None. Code is below. Any help is extremely appreciated.
import sys def search(list, target): min = 0 max = len(list)-1 avg = (min+max)/2 while (min < max): if (list[avg] == target): return avg elif (list[avg] < target): return search(list[avg+1:], target) else: return search(list[:avg-1], target) print "The location of the number in the array is", avg # The command line argument will create a list of strings # This list cannot be used for numeric comparisions # This list has to be converted into a list of ints def main(): number = input("Please enter a number you want to search in the array !") index = int(number) list = [] for x in sys.argv[1:]: list.append(int(x)) print "The list to search from", list print(search(list, index)) if __name__ == '__main__': main() CL : Anuvrats-MacBook-Air:Python anuvrattiku$ python binary_search.py 1 3 4 6 8 9 12 14 16 17 27 33 45 51 53 63 69 70 Please enter a number you want to search in the array !69 The list to search from [1, 3, 4, 6, 8, 9, 12, 14, 16, 17, 27, 33, 45, 51, 53, 63, 69, 70] 0 Anuvrats-MacBook-Air:Python anuvrattiku$ 5 Answers
In Python2 and Python3 you can use bisect as written in the comments. Replace your search with the following
from bisect import bisect_left def search(alist, item): 'Locate the leftmost value exactly equal to item' i = bisect_left(alist, item) if i != len(alist) and alist[i] == item: return i raise ValueError alist = [1,2,7,8,234,5,9,45,65,34,23,12] x = 5 alist.sort() # bisect only works on sorted lists print(search(a, x)) # prints 2 as 5 is on position 2 in the sorted list Also, the AS SortedCollection (Python recipe) could be useful.
The following code (from here) performs the binary search and returns position and if the item was found at all.
def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: pos = 0 midpoint = (first + last)//2 if alist[midpoint] == item: pos = midpoint found = True else: if item < alist[midpoint]: last = midpoint-1 else: first = midpoint+1 return (pos, found) Will return (2, True) if used in the example above.
Well, there are some little mistakes in your code. To find them, you should either use a debugger, or at least add traces to understand what happens. Here is your original code with traces that make the problems self evident:
def search(list, target): min = 0 max = len(list)-1 avg = (min+max)/2 print list, target, avg ... You can immediately see that:
- you search in a sub array that skips
avg-1when you are below avg - as you search in a sub array you will get the index in that subarray
The fixes are now trivial:
elif (list[avg] < target): return avg + 1 + search(list[avg+1:], target) # add the offset else: return search(list[:avg], target) # sublist ends below the upper limit That's not all, when you end the loop with min == max, you do not return anything (meaning you return None). And last but not least never use a name from the standard Python library for your own variables.
So here is the fixed code:
def search(lst, target): min = 0 max = len(lst)-1 avg = (min+max)/2 # uncomment next line for traces # print lst, target, avg while (min < max): if (lst[avg] == target): return avg elif (lst[avg] < target): return avg + 1 + search(lst[avg+1:], target) else: return search(lst[:avg], target) # avg may be a partial offset so no need to print it here # print "The location of the number in the array is", avg return avg The reason you aren't getting correct result is because in every recursive call your code is sending sliced array. So the array length keeps reducing. Ideally you should work out a way to send original array and work with only start, end indices.
@Serge Ballesta 's solution is undoubtly the correct answer to this question.
I am just going to add another way of solving this:
def search(arr, item, start, end): if end-start == 1: if arr[start] == item: return start else: return -1; halfWay = int( (end-start) / 2) if arr[start+halfWay] > item: return search(arr, item, start, end-halfWay) else: return search(arr, item, start+halfWay, end) def binarysearch(arr, item): return search(arr, item, 0, len(arr)) arr = [1, 3, 4, 6, 8, 9, 12, 14, 16, 17, 27, 33, 45, 51, 53, 63, 69, 70] print("Index of 69: " + str(binarysearch(arr, 69))) # Outputs: 16 Recursive:
def in_list(l, x): if len(l) < 2: if l[0] == x: return True else: return False mid = len(l) // 2 if x < l[mid]: return in_list(l[:mid], x) else: return in_list(l[mid:], x) or iterative:
def in_list2(l, x): low = 0 high = len(l) - 1 while low <= high: mid = (low + high) // 2 if l[mid] == x: return True if x < l[mid]: high = mid - 1 else: low = mid + 1 return False 
