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"

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. — Lasse V. Karlsen, Feb 29 '12 at 14:58
May want to see [binary-search-in-python](http://stackoverflow.com/questions/212358/binary-search-in-python) — nawfal, Jun 15 '14 at 19:22
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. — RBF06, Feb 22 '19 at 23:11

score 22 · Answer 1 · edited Jan 28 '18 at 01:22

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

@user1342336 Binary search is only expected to work on lists that are already in sorted order. — Arthur Tacca, Jul 16 '20 at 21:44

score 18 · Answer 2 · answered Feb 29 '12 at 15:44

18

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

answered Feb 29 '12 at 15:44

Pierce

564
2
8

Ecir Hana · Answer 3 · 2016-03-26T00:55:58.870

13

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

edited Mar 26 '16 at 00:55

answered Feb 29 '12 at 15:02

Ecir Hana

10,864
13
67
117

2

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. – Shnatsel Mar 25 '16 at 15:42
9

@Shnatsel 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`](http://docs.python.org/library/sys.html#sys.setrecursionlimit)) we are talking about arrays of sizes up to 2**1000, also know as ~10^300... – Ecir Hana Mar 26 '16 at 00:53

score 10 · Accepted Answer · answered Feb 29 '12 at 15:01

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.

Good performance note; it is important for the OP to consider that — PALEN, Sep 29 '17 at 00:23

score 2 · Answer 5 · answered Feb 29 '12 at 15:59

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.

score 1 · Answer 6 · edited Sep 29 '20 at 20:00

1

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)

edited Sep 29 '20 at 20:00

Community

1
1

answered Nov 01 '16 at 12:38

maysara

5,873
2
23
34

score 1 · Answer 7 · edited Jan 10 '18 at 10:55

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)

score 1 · Answer 8 · answered Sep 15 '17 at 13:23

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)

score 1 · Answer 9 · edited May 05 '18 at 00:34

1

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)

edited May 05 '18 at 00:34

Stephen Rauch

47,830
31
106
135

answered May 05 '18 at 00:13

Mike

458
4
13

This doesn't handle if the item doesn't exist in the list. It just throws exception. – ozn Nov 21 '19 at 04:28

score 0 · Answer 10 · answered Jan 03 '17 at 21:50

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)

nettrino · Answer 11 · 2017-02-07T03:54:08.600

0

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:])

edited Feb 07 '17 at 03:54

answered Feb 07 '17 at 03:48

nettrino

588
6
21

score 0 · Answer 12 · answered Mar 17 '19 at 16:46

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

score 0 · Answer 13 · answered Feb 29 '12 at 14:59

0

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.

answered Feb 29 '12 at 14:59

macduff

4,655
18
29

score 0 · Answer 14 · answered Feb 29 '12 at 15:00

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?

Binary search algorithm in python

14 Answers14

Linked

Related