Binary search in a Python list

Question

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$ 

Answer 1

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(alist, 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.

Answer 2

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-1 when 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

Answer 3

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

Answer 4

@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

Answer 5

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.