Binary Search

Nov. 11, 2020

Vuong Huynh

Binary Search

Suppose we have an array and want to search an element in it, searching from beginning to end of the array or vice versa will take O(n) efficiency.

Binary search is an efficient algorithm for searching an element in a sorted array (or list). It divides the sorted arrayed repeatedly into two parts and narrows down the location of the searched element.

Example: we want to search number 10 in the array [1, 2, 3, 4, 5, 6, 7, 8]

First, we divide the array into two parts [1, 2, 3, 4] and [5, 6, 7, 8]
We can see numbers 4 and 5 are in the middle of the array. Compare 10 to 4 (left side).
Since 10 > 4 ⁽¹⁾, we narrow down the array by continuing to search our number in the second half part [5, 6, 7, 8]
In the second half part, we repeat the division: [5, 6] and [7, 8]
Now we have 6, and 7 are in the middle. Compare 10 to 6 (left side again).
Because 10 > 6 ⁽²⁾, we can narrow down the location of searched number in [7, 8]
We divide the array [7, 8] once again into [7] and [8] then compare the searched number with [7]
Compare 10 to 7 ⁽³⁾, not match. Compare 10 to 8 ⁽⁴⁾, not match either.
Finally, we know the number we want to search for is not in the entire array.

The efficiency of Binary Search:

From (1), (2), (3), and (4) in the example above, we can create a table to count the number of iterations.

Array size	0	1	2	3	4	5	6	7	8
Iterations	0	1	2	2	3	3	3	3	4

From the table, we can see that every time the array is doubled in size, it takes an extra iteration of the algorithm to get through it.

Which means the array size of 1 or 2⁰ has 1 iteration (0 + 1). When an array size of 2 or 2¹ has 2 iterations (1 + 1), an array size of 4 or 2² has 3 iterations (2 + 1), and an array size of 8 or 2³ has 4 iterations (3 + 1).

From this observation, we can conclude that efficiency is the exponent of 2 + 1 or O(log₂(n) + 1):

With approximation, we have the efficiency of Binary Search:

`O``(log(n))`

A good source to visualize the Binary Search.

Practice from Udacity

"""You're going to write a binary search function.
You should use an iterative approach - meaning
using loops.
Your function should take two inputs:
a Python list to search through, and the value
you're searching for.
Assume the list only has distinct elements,
meaning there are no repeated values, and 
elements are in a strictly increasing order.
Return the index of value, or -1 if the value
doesn't exist in the list."""

def binary_search(input_array, value): 
    low = 0
    high = len(input_array) - 1
    mid = 0
  
    while low <= high: 
        mid = (high + low) // 2
         
        if input_array[mid] < value: 
            low = mid + 1
  
        elif input_array[mid] > value: 
            high = mid - 1
  
        else: 
            return mid 
  
    return -1
  
  
# Test array 
test_list = [1,3,9,11,15,19,29]
test_val1 = 25              
test_val2 = 15
print(binary_search(test_list, test_val1))  # -1 - return -1 since 25 is not in the list
print(binary_search(test_list, test_val2))  # 4 - return 4 since 15 has index of 4 in the list

Binary Search

Binary Search

O(log(n))

`O``(log(n))`