Binary search divides a sorted array into two halves, compares the key with the middle element, and conquers by searching only the half that can contain the key.
Divide and conquer steps:
- Divide: find the middle index \(mid = \lfloor(low + high)/2\rfloor\).
- Conquer: if
key == a[mid], the search is successful. Ifkey < a[mid], search the left half \([low, mid-1]\); otherwise search the right half \([mid+1, high]\). - Combine: nothing to combine; the answer of the sub-problem is the answer.
- If \(low > high\), the key is not present.
BinSearch(a, low, high, key):
if low > high: return -1
mid = (low + high) / 2
if key == a[mid]: return mid
else if key < a[mid]:
return BinSearch(a, low, mid - 1, key)
else:
return BinSearch(a, mid + 1, high, key)
Example: search for 23 in a = [5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 to 8).
- low = 0, high = 8, mid = 4: a[4] = 23 = key. Found at index 4.
Search for 72:
- mid = 4, a[4] = 23 < 72, so search right half: low = 5.
- low = 5, high = 8, mid = 6: a[6] = 56 < 72, so low = 7.
- low = 7, high = 8, mid = 7: a[7] = 72. Found at index 7.
Time complexity: each step halves the problem, so \(T(n) = T(n/2) + c\), which gives \(T(n) = O(\log n)\). Best case \(O(1)\) (key at the middle). The array must be sorted.