Binary search algorithm in python

Question

I am trying to implement the binary search in python and have written it as follows. However, I can't make it stop whenever needle_element is larger than the largest element in the array.

Can you help? Thanks.

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"

Exudation

I would try to avoid creating lots of partial copies of the array, and pass in a lower and upper index instead. Then you simply stop if lower>upper. – Baynebridge

May want to see binary-search-in-python – Whilst

If the purpose of this is academic understanding of binsearch, I can't really help, but if the purpose of this code is to actualy be used: never roll your own binsearch. Always use widly adopted, and prefereably old, library implementation, and even then be very careful, binseach is notoriously difficult to get right in all edgecases. – Pottage

Answer 1

In the case that needle_element > array[mid], you currently pass array[mid:] to the recursive call. But you know that array[mid] is too small, so you can pass array[mid+1:] instead (and adjust the returned index accordingly).

If the needle is larger than all the elements in the array, doing it this way will eventually give you an empty array, and an error will be raised as expected.

Note: Creating a sub-array each time will result in bad performance for large arrays. It's better to pass in the bounds of the array instead.

Camembert

Good performance note; it is important for the OP to consider that – Sheley

Answer 2

It would be much better to work with a lower and upper indexes as Lasse V. Karlsen was suggesting in a comment to the question.

This would be the code:

def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x

• lower < upper will stop once you have reached the smaller number (from the left side)
• if lower == x: break will stop once you've reached the higher number (from the right side)

Example:

>>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None

Foilsman

This doesn't work. Try a list: [7,9,2,4,8,6,5,1,8,5,3]. – Stavro

You could do x = (lower + upper) // 2 – Freehearted

@Stavro Binary search is only expected to work on lists that are already in sorted order. – Nunnally

Answer 3

Why not use the bisect module? It should do the job you need---less code for you to maintain and test.

Winny

Answer 4

array[mid:] creates a new sub-copy everytime you call it = slow. Also you use recursion, which in Python is slow, too.

Try this:

def binarysearch(sequence, value):
    lo, hi = 0, len(sequence) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sequence[mid] < value:
            lo = mid + 1
        elif value < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None

Vaticinate

Not only recursion is slow - it will actually blow up in your face if the array is long enough, because Python has no tail recursion optimization and will run out of stack frames given a large enough input array. – Convulsant

@Convulsant ad "large enough input array" - given we are talking about "binary" search and CPython has by default recursion limit set to 1000 (can be set to more by sys.setrecursionlimit) we are talking about arrays of sizes up to 2**1000, also know as ~10^300... – Vaticinate

Answer 5

You can improve your algorithm as the others suggested, but let's first look at why it doesn't work:

You're getting stuck in a loop because if needle_element > array[mid], you're including element mid in the bisected array you search next. So if needle is not in the array, you'll eventually be searching an array of length one forever. Pass array[mid+1:] instead (it's legal even if mid+1 is not a valid index), and you'll eventually call your function with an array of length zero. So len(array) == 0 means "not found", not an error. Handle it appropriately.

Nano

Answer 6

All the answers above are true , but I think it would help to share my code

def binary_search(number):
    numbers_list = range(20, 100)
    i = 0
    j = len(numbers_list)
    while i < j:
        middle = int((i + j) / 2)
        if number > numbers_list[middle]:
            i = middle + 1
        else:
            j = middle
    return 'the index is '+str(i)

Purity

Answer 7

def binary_search(array, target):
    low = 0
    mid = len(array) / 2
    upper = len(array)

    if len(array) == 1:
        if array[0] == target:
            print target
            return array[0]
        else:
            return False
    if target == array[mid]:
        print array[mid]
        return mid
    else:
        if mid > low:
            arrayl = array[0:mid]
            binary_search(arrayl, target)

        if upper > mid:
            arrayu = array[mid:len(array)]
            binary_search(arrayu, target)

if __name__ == "__main__":
    a = [3,2,9,8,4,1,9,6,5,9,7]
    binary_search(a,9)

Stavro

Answer 8

This is a tail recursive solution, I think this is cleaner than copying partial arrays and then keeping track of the indexes for returning:

def binarySearch(elem, arr):
    # return the index at which elem lies, or return false
    # if elem is not found
    # pre: array must be sorted
    return binarySearchHelper(elem, arr, 0, len(arr) - 1)

def binarySearchHelper(elem, arr, start, end):
    if start > end:
        return False
    mid = (start + end)//2
    if arr[mid] == elem:
        return mid
    elif arr[mid] > elem:
        # recurse to the left of mid
        return binarySearchHelper(elem, arr, start, mid - 1)
    else:
        # recurse to the right of mid
        return binarySearchHelper(elem, arr, mid + 1, end)

Geri

Answer 9

Using Recursion:

def binarySearch(arr,item):
    c = len(arr)//2
    if item > arr[c]:
       ans = binarySearch(arr[c+1:],item)
       if ans:
          return binarySearch(arr[c+1],item)+c+1
    elif item < arr[c]:
       return binarySearch(arr[:c],item)
    else:
       return c

binarySearch([1,5,8,10,20,50,60],10)

Valetudinarian

This doesn't handle if the item doesn't exist in the list. It just throws exception. – Diuretic

Answer 10

If you're doing a binary search, I'm guessing the array is sorted. If that is true you should be able to compare the last element in the array to the needle_element. As octopus says, this can be done before the search begins.

Impenitent

Answer 11

You can just check to see that needle_element is in the bounds of the array before starting at all. This will make it more efficient also, since you won't have to do several steps to get to the end.

if needle_element < array[0] or needle_element > array[-1]:
    # do something, raise error perhaps?

Curvy

Answer 12

It returns the index of key in array by using recursive.

round() is a function convert float to integer and make code fast and goes to expected case[O(logn)].

A=[1,2,3,4,5,6,7,8,9,10]
low = 0
hi = len(A)
v=3
def BS(A,low,hi,v):
    mid = round((hi+low)/2.0)
    if v == mid:
        print ("You have found dude!" + " " + "Index of v is ", A.index(v))
    elif v < mid:
        print ("Item is smaller than mid")
        hi = mid-1
        BS(A,low,hi,v)
    else :
        print ("Item is greater than mid")
        low = mid + 1
        BS(A,low,hi,v)
BS(A,low,hi,v)

Monkish

Answer 13

Without the lower/upper indexes this should also do:

def exists_element(element, array):
    if not array:
        yield False

    mid = len(array) // 2
    if element == array[mid]:
        yield True
    elif element < array[mid]:
        yield from exists_element(element, array[:mid])
    else:
        yield from exists_element(element, array[mid + 1:])

Coorg

Answer 14

Returning a boolean if the value is in the list.

Capture the first and last index of the list, loop and divide the list capturing the mid value. In each loop will do the same, then compare if value input is equal to mid value.

def binarySearch(array, value):
  array = sorted(array)
  first = 0
  last = len(array) - 1

  while first <= last:
    midIndex = (first + last) // 2
    midValue = array[midIndex]

    if value == midValue:
      return True
    if value < midValue:
      last = midIndex - 1
    if value > midValue:
      first = midIndex + 1
  return False

Feune