Binary Search

Internal

• Algorithms | Divide and Conquer

Organizatorium

• Binary search can be applied to sorted or unsorted array. Provide time complexity analysis.

Running Time Analysis with Master Theorem

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 Case 1 of the master theorem, so the running time upper bound is O(n⁰log n) = O(log n).