#Binary Search and Variations
- Idea: cut search space in half (about half) by asking only one question.
- Also work when, with constant time, cut search space from n to n
a, where a > 1. - Used often in computer science.
- Pure binary search
x1, x2, . . . , xn is a sequence of real numbers such that
x1 ≤ x2 ≤ · · · ≤ xn
Problem: Given a real number z, we want to find whether z appears in the sequence, and
if it does, to find an index i such that xi = z.
Solution: binary search!
Binary search:
Question: “Is xn/2 < z?”
Yes: binary search range becomes xn/2+1, . . . xn
No: binary search range becomes x1, . . . , xn/2
Complexity: O(log2 n).
#A More General Version
Input: a sorted sequence, x1 ≤ x2 ≤ . . . ≤ xn, and a target value z
Output: the largest index i, s.t. xi ≤ z, if there is no such i then return 0;
- If x1 > z, return 0;
- If xn ≤ z, return n;
- l = 1; r = n; (xl ≤ z < xr)
- if l = r − 1 return l;
- Set m to b
l+r/2，the greatest integer less than or equal to l+r/2
which is the middle between l and r - if xm > z, then r = m; goto step 4;
- if xm ≤ z, then l = m; goto step 4;
#Binary Search in a Cyclic Sequence
Definition. A sequence x1, x2, . . . , xn is said to be cyclically sorted if the smallest
number in the sequence is xi
for some unknown i, and the sequence
xi
, xi+1, . . . , xn, x1, x2, . . . , xi−1
is sorted.
The Problem: Given a cyclically sorted list, find the position of the minimum element in
the list (we assume elements are distinct).
Solution: For any two numbers xk, xm, such that k < m, compare xk with xm.
- If xk < xm then i cannot be in the range k < j ≤ m (k is possible)
- If xk > xm then i must be in the range k < j ≤ m
Is xn/2 < xn?
Yes: search range 1 . . . n/2. No: search range n/2 + 1, . . . n.
Find the index of the smallest element in O(logn) time