Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Idea

Binary search finds a key in an array L sorted in non-decreasing order, . It is the array version of searching a binary search tree.

Steps:

  • compute the midpoint of the current range L[i..j]
  • if L[k] == key, the record is found
  • if key < L[k], the key can only be in the left part, so set j = k - 1
  • if key > L[k], the key can only be in the right part, so set i = k + 1
  • stop with -1 when i > j, i.e. the range is empty

Code

def binary_search(L, key):
    i = 0
    j = len(L) - 1
    while i <= j:
        k = (i + j) // 2
        if key == L[k]:
            return k
        if key < L[k]:
            j = k - 1              # search the first part
        else:
            i = k + 1              # search the second part
    return -1
 
L = [-2, 3, 7, 10, 17]
print(binary_search(L, 17))        # 4
print(binary_search(L, 2))         # -1

Example 1: Key Found

With L = [3, 14, 15, 17, 28, 31, 40, 51] and key : , then , then , then where L[7] == 51, so it returns 7.

Example 2: Key Not Found

Same array, key :

LoopAction
107317, set
247531, set
344428, set
end54, return

Worst-Case Complexity

Each comparison (cost ) halves the range:

The halving stops when one element is left, , so and

Sequential versus Binary

Sequential search is and binary search is . Since , a sorted list of one million elements may need one million comparisons with sequential search but only about 20 with binary search. The catch is that the array must be sorted first.