Binary Search Cutaway

What is binary search?

Binary search is an algorithm for searching elements from a sorted array. It far outweighs in benefits compared to a linear search method.

In this algorithm – implemented iteratively or recursively – the mid of the sorted array is found by the formula (low+high)//2, high and low being the indices of the extreme ends of the sorted array. Each time an answer is arrived, the result is compared with the target value. If a match is found on that iteration, then mid becomes the found value along with its index. If there is no success, subsequent iterations have to be done with the formula, moving and resizing the low-high window, until the element is found or the entire array has been searched with no success.

Complexity

1. Best case time complexity: \(O(1)\)
2. Average case time complexity: \(O(log_2 N)\)
3. Worst case time complexity: \(O(log_2 N)\)

Space complexity:

1. Iterative method: \(O(1)\)
2. Recursive method: \(O(log_2 N)\)

Now, compare these values with the time complexity values of Linear search:

1. Best case: \(O(1)\)
2. Average case: \(O(N)\)
3. Worse case: \(O(N)\)

Space complexity:

1. Space complexity of linear search: \(O(1)\)
2. Number of comparisons in best case: 1
3. Number of comparisons in worst case: N

The best case in both scenarios remains the same; but comparison starts for the average and the worst cases and that is where binary search is clearly ahead.

What makes Binary Search special and different is its complexity. The algorithm uses only \(O(logN)\) time for average and worst cases. This can be quite advantageous when searching huge arrays for an element very quickly. Compare this with other searching algorithms such as linear search. The average and worst case time complexities come to \(O(N)\).

A binary search performs much better even if the element to be searched lies at the end of the array. Whereas a linear search would traverse the entire array to get the last element and waste a lot of time, there is no such thing as a traversal of an array in binary search and hence is much faster.

What is special about this implementation?

Our implementation gives a cutaway view of the Binary Search algorithm. It prints the low, mid and high pointer positions and helps us learn how they move and converge till the search terminates with a success or failure.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#Binary search using iterative method

def binarysearch(arr,elem,animation=False):
    '''Binary search using iterative method.
       Input:array and element to search
       Output:index of element found, else None'''
       
    low = 0
    high = len(arr)-1
    mid = (low+high)//2
    
    _arr = sorted(arr)   #sort the array
    
    for e in _arr:
        print(f'{e: >5}', end='')
    print()
    
    while (high >= low):
        if (animation):
            bar = ['' for i in range(len(_arr))] #init empty bar
            bar[low] += 'L' #place H,M,L markers at proper positions
            bar[mid] += 'M'
            bar[high] += 'H'
            for e in bar:
                print(f'{e: >5}',end='')
            print(f'    {low},{mid},{high}')
            
        if elem == _arr[mid]:  #element found
            return mid
                       
        if elem < _arr[mid]:   #shift the search window.
            high = mid-1            
        else:  
            low = mid+1

        mid = (low+high)//2
        
    return None         #Nothing found

if __name__ == "__main__":
    arr = [2,3,4,5,6,7,18,21,1,9,45,100]
    elem = 2
    print(f'Found {elem} at pos: {binarysearch(arr,elem,animation=True)}')

Sample run of the code

    1    2    3    4    5    6    7    9   18   21   45  100
    L                        M                             H    0,5,11
    L         M         H                                       0,2,4
   LM    H                                                      0,0,1
       LMH                                                      1,1,1
Found 2 at pos: 1

The code is a conventional binary search code with the ‘animation’ part(highlighted) which takes care of printing the high, mid and low values after each iteration.

How to use this source code to learn about binary search?

Just run the program as it is and observe the output. Note where the low, mid and high symbols travel on each iteration and where they end in the final iteration. Compare observations of finding an element and not finding an element and see where the three labels stand.

Try out:

• arrays of different length(odd/even)
• with repeating values
• finding values that don’t exist in the list.

Let us verify that the number of iterations is indeed \(O(log_2 n)\). We have 12 elements in our array. The next power of 2 after 12 is 16. We consistently observe that the number of iterations in the worst case is \(log_2 16\).