Binary Search

Internal

• Algorithms | Divide and Conquer

Overview

Binary search is the implementation of the SEARCH operation for both sorted and unsorted arrays. In case of sorted arrays, because we know that once the problem is divided in two, the key we aim for can only be in just one half of the array, the running time is O(log n). 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