Binary Search Algorithm In Python

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

Solution 1:

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:

defbinary_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 linesbreak# 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

Solution 2:

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

Solution 3:

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

Try this:

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

Solution 4:

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.

Solution 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.