Binary Search

Internal

• Algorithms | Divide and Conquer

TODO

Update from Algorithms Illuminated.

Overview

Binary search is the implementation of the SEARCH operation for both unsorted and sorted arrays.

In case of sorted arrays, we look at the element in the middle. If it's the element we're looking for, the algorithm finishes. If it is not, we recursively look in the left half if the element that we're looking for is smaller than the element in the middle, and in the right half otherwise. At each recurrence step the problem is divided in two, and we are only looking at the half of the problem, so the running time is O(log n). A more detailed analysis using master theorem is available below in the Running Time Analysis with Master Theorem section.

For an unsorted array, we need to look in both halves.

Running Time Analysis with Master Theorem

Sorted Arrays

For a binary search on a sorted array, we know upfront whether the number we search is in the first half or in the second half by looking at the element in the middle, so we recurse only once - we split the problem in one smaller sub-problem (a=1). The size of the subproblem is half (b=2). Upon exiting from recursion, we already have the result, so no more work is necessary in the combine phase, the combine phase is O(1) = O(n⁰), thus d=0. a/b^d = 1/2⁰ = 1, we find ourselves in master method's Case 1 of the master theorem, so the running time upper bound is O(n⁰log n) = O(log n).

Unsorted Arrays

TODO

Canonical Use

• The 2-SUM Problem