Computer Science

Mastering Binary Search

An exploration of the binary search algorithm, showing how divide-and-conquer strategy achieves logarithmic time complexity by repeatedly halving the search space.

A = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]

Imagine searching for a word in a dictionary. Because the words are sorted, you don't look at every page. You start in the middle. The fundamental rule for binary search is that the data must be sorted first, otherwise, there is no logic to determine which half to discard.

Step-by-step solver

(a) Precondition

The array must be sorted in ascending order to allow elimination of elements.

A = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]

(b) Setup

Initialize pointers low at 0 and high at n-1.

low = 0, high = n - 1

Calculate midpoint and compare; update pointers based on target value relative to middle element.

mid = \lfloor (low + high) / 2 \rfloor

(d) Termination

If target is found return index, else if pointers cross return not found.

low > high \Rightarrow \text{return 'not found'}

(e) Complexity

Since each step halves the remaining array, the growth is logarithmic.

O(\log n)

Original question

Explain how the binary search algorithm works on a sorted array, and state its time complexity in big-O notation.

Follow-up chat

Ask me anything about this lesson. I'll answer using what we just covered.