5

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$
Improve this question
8
  • 4
    You do know, that binary search requires a sorted array/list to work? It's not the only wrong thing with your algorithm. And BTW, never ever call a variable list or any other built-in type or function. And why do you print inside a function that returns arg. It won't ever be printed. Commented Jul 13, 2016 at 8:12
  • 2
    Also there's binary search built in: docs.python.org/3/library/bisect.html Commented Jul 13, 2016 at 8:14
  • @jonrsharpe I believe that is a homework assignment. Commented Jul 13, 2016 at 8:15
  • @EliKorvigo that seems very probable. Commented Jul 13, 2016 at 8:15
  • @Eli Korvigo : Yes I am aware that it needs a sorted list. I have edited to display the command line arguments. I dont understand why it is not printing the index of the element. I tried commenting the print statement in the function but it still prints 0. That is what is not clear to me Commented Jul 13, 2016 at 8:22

5 Answers 5

Reset to default
25

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

In the first code segment, don't you mean print(search(alist,x))?
what is 'a'? It's still 'a' and not 'alist', so it should be 'a'?
I just corrected the code to read alist in the first snippet, as in print(search(alist, x)), as previous commenters indicated, rather than the previous (incorrect) print(search(a, x)).
7

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
Improve this answer

3 Comments

could you explain your point of ending the loop with min==max a bit
min and max are standard variable names*
Agreed with @JacobIRR, consider use low/high instead of min/max.
2

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
Improve this answer

Comments

1

@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
Improve this answer

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.