Binary search of an integer array

Question

I'm a beginner. This is my implementation of binary search algorithm in Python. Please review my code and give your valuable inputs for further improvements on overall coding style, rare cases etc.

def binary_search(arr,value):
    left = 0
    right = len(arr) - 1
    while(left <= right):
        mid = (left + right) // 2
        print(mid)
        if arr[mid] is value:
            return mid
        elif value < arr[mid]:
            right = mid - 1
        elif value > arr[mid]:
            left = mid + 1

    return -1

def print_binary_search(arr,value):
    pos = binary_search(arr,value)
    if pos is -1:
        print("Element not found")
    else:
        print("Element found in the positon " +str(pos))



def test1():
    arr = [2,5,8,9,11,15,17,19,22,26,29,33,56]
    value = 56
    print_binary_search(arr,value)

def test2():
    arr = [2,5,8,9,11,15,17,19,22,26,29,33,56]
    value = 59
    print_binary_search(arr,value)


test1()
test2()

Answer 1

1. Review

1. There's no docstring. It's a good idea to write a specification for each function you write — without knowing what a function is supposed to do, it's impossible to check that the implementation is correct. In this case I'd write:

   def binary_search(arr, value):
       """Given a sorted sequence arr, return an index i such that arr[i] == value.
       Return -1 if no element in arr is equal to value.
   
       """
   

   (Note that this doesn't say what happens if there are more than one index i meeting the condition — you might want to say "return the leftmost index" or "return the rightmost index" if you care about this.)

2. The line print(mid) seems to have been accidentally left over after a debugging session.

3. The function binary_search has a chain of tests if condition1: ... elif condition2: ... with no else: on the end. Whenever you spot this pattern, you should always be suspicious, because what if none of the conditions is true? In this case I'd write:

   if arr[mid] == value:
       return mid
   elif value < arr[mid]:
       right = mid - 1
   else: # value > arr[mid]
       left = mid + 1
   

   This makes it clear that exactly one of the three cases has to happen.

4. The code evaluates arr[mid] up to three times. It would slightly faster to evaluate it just once and remember the result in a local variable:

   mid_value = arr[mid]
   if mid_value == value:
       return mid
   elif value < mid_value:
       right = mid - 1
   else: # value > mid_value
       left = mid + 1
   

5. In programming, it's often more convenient to represent a range of numbers in "half-open" form — that is, inclusive on the lower end and exclusive on the higher end. This reduces the number of operations and helps avoid off-by-one errors.

   In this case, there is a subtraction in two places:

   right = len(arr) - 1
   # ...
   right = mid - 1
   

   By keeping the range from left to right in half-open form, both of these subtractions could be avoided. The condition on the while loop would then become:

   while left < right:
   

6. Each time around the while loop, the code tests (up to) four conditions:

   while left <= right:
   if arr[mid] == value:
   elif value < arr[mid]:
   elif value > arr[mid]:
   

   I showed above how to reduce this to three. But it is possible to reduce it to two by omitting the test arr[mid] == value, like this:

   left = 0
   right = len(arr)
   while left < right:
       mid = (left + right) // 2
       if arr[mid] < value:
           left = mid + 1
       else: # arr[mid] >= value
           right = mid
   

   It's a good idea to play with some examples to see how this works — the idea is that when arr[mid] == value you set right = mid and then subsequent loops just increase left until left == right and then the while loop exits.

7. The code handles the exceptional situation (the value is not found in the sequence) by returned an exceptional value (−1). This is an error-prone design because it would be very easy for the caller to forget to check for the exceptional value. It would be easy to write:

   i = binary_search(my_array, my_value)
   found_value = my_array[i]
   

   which would go wrong when i is -1. It's better to handle an exceptional situation by raise an exception.

2. Revised code

def binary_search(arr, value):
    """Given a sorted sequence arr, return the leftmost i such that
    arr[i] == value. Raise ValueError if no element in arr is equal
    to value.

    """
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        if value > arr[mid]:
            left = mid + 1
        else:
            right = mid
    if left != len(arr) and arr[left] == value:
        return left
    else:
        raise ValueError("{!r} is not in sequence".format(value))

3. Using bisect module

Python has a built-in bisect module for searching sorted sequences. If you look at the section "Searching Sorted Lists" you'll see that your function can be implemented like this:

from bisect import bisect_left

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Answer 2

1. if arr[mid] is value:

   You don't want to compare two integers with is, which compares identity. Use == instead. is will break your code when using large or small numbers (\$<-5\$, \$>256\$).

   For example, using is with this "test" function:

   def test1():
       arr = list(range(257, 270))
       value = 260
       print_binary_search(arr, value)
   

   Results with an infinite loop.

   Using == works as expected and returns 3.

   The reason is that Python uses integer caching for the range \$[-5, 256]\$.

And some PEP8 nitpicking:

2. while(left <= right):

   The parenthesis around the condition are useless in this case, you should prefer a whitespace:

   while left <= right:
   

3. You are missing some whitespaces after commas in function definition, function calls, list literals and around operators.

   For example, your code should look like this (relevant lines only):

   def print_binary_search(arr, value):
   
   #######
   
   pos = binary_search(arr, value)
   
   #######
   
   arr = [2, 5, 8, 9, 11, 15, 17, 19, 22, 26, 29, 33, 56]
   
   #######
   
   print("Element found in the position " + str(pos))
   

Answer 3

and according to a recent hot discussion on SO.

you should use mid = left + (right-left)/2 instead of mid = (left+right)/2 to avoid possible overflows