Binary Search Without a Sorted Array
What binary search really needs
The search in Introduction to Binary Search worked because the array was sorted. But look at what the loop actually used: at mid, one test that said which half still holds the answer. Sorted order is one way to get that test. It isn't the only one.
This lesson is four arrays that aren't sorted, each with its own test at mid: a rotated sorted array, an array with a peak, a sorted array of pairs with one single value, and a mountain. Each test keeps an answer inside [lo, hi] and shrinks the range, so each is still O(log n).
Rotated sorted arrays: one half is always sorted
Search in Rotated Sorted Array takes a sorted array that's been rotated, like [4, 5, 6, 7, 0, 1, 2], and asks for a target's index. Cut the range at mid, and the drop (the one place a value is followed by a smaller one) can be in only one half. The other half is sorted.
Which one? If nums[lo] <= nums[mid], the left half has no drop, so it's sorted. Otherwise the right half is. In a sorted half you can tell in one check whether the target is there: is it between that half's two ends? If yes, keep that half; if no, keep the other.
Looking for 0 in [4, 5, 6, 7, 0, 1, 2]:
Searching a rotated array — The shaded range still holds the target if it's there. At each mid, the sorted half decides which side to keep.
int searchRotated(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // the left half [lo, mid] is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // the right half [mid, hi] is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # the left half [lo, mid] is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1 # the target is in the sorted half
else:
lo = mid + 1
else: # the right half [mid, hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1 # the target is in the sorted half
else:
hi = mid - 1
return -1
static int searchRotated(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // the left half [lo, mid] is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // the right half [mid, hi] is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
function searchRotated(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) { // the left half [lo, mid] is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // the right half [mid, hi] is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
Each prints 4, -1, -1, 1 and 0 for 0 in [4, 5, 6, 7, 0, 1, 2], 3 in [4, 5, 6, 7, 0, 1, 2], 0 in [1], 1 in [3, 1] and 5 in [5, 1, 3]. Note the <= in nums[lo] <= nums[mid]: when lo == mid, the left half is one value, and one value is sorted.
The minimum is a first yes
Find Minimum in Rotated Sorted Array is the first-yes search from Introduction to Binary Search in disguise. Ask "is nums[i] at most the last value?" along the array. Every value before the drop is bigger than the last value (no), and every value from the minimum on is at most the last value (yes). The answers flip once, and the minimum is the first yes.
So compare nums[mid] with nums[hi]. If it's bigger, mid is before the drop: lo = mid + 1. Otherwise the minimum is mid or to its left: hi = mid.
Finding the minimum of a rotated array — Each step compares nums[mid] (amber when it's before the drop) with nums[hi] (glowing).
int findMin(const vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; // mid is before the drop: the minimum is to its right
else hi = mid; // mid is at or after the drop: the minimum is mid or left of it
}
return nums[lo];
}
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # mid is before the drop: the minimum is to its right
else:
hi = mid # mid is at or after the drop: the minimum is mid or left of it
return nums[lo]
static int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; // mid is before the drop: the minimum is to its right
else hi = mid; // mid is at or after the drop: the minimum is mid or left of it
}
return nums[lo];
}
function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] > nums[hi]) lo = mid + 1; // mid is before the drop: the minimum is to its right
else hi = mid; // mid is at or after the drop: the minimum is mid or left of it
}
return nums[lo];
}
Each prints 1, 0, 11 and 1. The index where lo ends is how far the array was rotated: 4 for [4, 5, 6, 7, 0, 1, 2]. That's the whole of Rotation Count in a Rotated Sorted Array.
Duplicates: when you can't tell
Search in Rotated Sorted Array II allows repeated values, and that breaks the test. In [1, 1, 1, 2, 1], nums[lo], nums[mid] and nums[hi] are all 1: the drop could be in either half. All you can safely do is drop one copy from each end (lo += 1; hi -= 1) and look again.
def search_rotated_dups(nums, target):
lo, hi, looks = 0, len(nums) - 1, 0
while lo <= hi:
looks += 1
mid = (lo + hi) // 2
if nums[mid] == target:
return True, looks
if nums[lo] == nums[mid] == nums[hi]: # no half can be shown sorted: drop one copy from each end
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False, looks
On an array of 1,500 ones, a 2, and 500 more ones (a rotation of 2,000 ones followed by a 2), it finds the 2 after 510 looks: that's linear, not logarithmic. It can't be helped. Until a comparison lands on the 2, every look sees only 1s, so no rule can tell which half hides it. With duplicates, the worst case is O(n).
Peaks: walk uphill
Find Peak Element wants any index whose value beats both neighbours (the ends count the outside as minus infinity). The array is in no order at all, but there's still a test. Compare nums[mid] with nums[mid + 1]. If the next value is bigger, you're on an uphill slope, and a peak must lie to the right: the values can't keep rising past the end of the array. If it's smaller, mid itself or something to its left is a peak. Either way the range keeps a peak and shrinks.
def find_peak(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # uphill to the right: a peak is to the right of mid
else:
hi = mid # downhill: mid or something to its left is a peak
return lo
It returns 2 for [1, 2, 3, 1] and 5 for [1, 2, 1, 3, 5, 6, 4] (index 1 is also a peak there; any peak is a correct answer). Find a Peak Element II does the same in a grid: take the middle column's largest value, then step toward a bigger neighbour column.
Single Element in a Sorted Array: count by pairs
Every value appears twice except one, and the array is sorted, so copies sit side by side. Before the single value, every pair starts at an even index: (0, 1), (2, 3), …. After it, the pairs are shifted and start at odd indices. So at an even mid, ask "is nums[mid] different from nums[mid + 1]?" That's no before the single and yes from it on: a first yes again, over even indices only.
def single_non_duplicate(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1:
mid -= 1 # look at the start of a pair: an even index
if nums[mid] == nums[mid + 1]:
lo = mid + 2 # the pair is whole: the single is after it
else:
hi = mid # the pair is broken: the single is at mid or before
return nums[lo]
It returns 2 for [1, 1, 2, 3, 3, 4, 4, 8, 8] and 10 for [3, 3, 7, 7, 10, 11, 11]. The mid -= 1 that makes mid even matters, as the mistakes below show.
Mountains: find the peak, then search both sides
Find in Mountain Array gives an array that rises, then falls, and asks for the first index of a target. It's three binary searches: the peak by the slope test, then an ordinary search on the rising side (which goes up), then one on the falling side (which goes down, so the comparisons flip). The rising side comes first, so the first index found there is the smallest.
def find_in_mountain(target, arr):
n = len(arr)
lo, hi = 0, n - 1
while lo < hi: # 1. the peak, by the slope
mid = (lo + hi) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
peak = lo
lo, hi = 0, peak # 2. the rising side, which goes up
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
lo, hi = peak + 1, n - 1 # 3. the falling side, which goes down
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] > target:
lo = mid + 1
else:
hi = mid - 1
return -1
It returns 2 for 3 in [1, 2, 3, 4, 5, 3, 1] and -1 for 3 in [0, 1, 2, 4, 2, 1]. Three searches of O(log n) each is still O(log n), which is what the problem's limit on calls to the array is about.
Common mistakes
Comparing with the left end in Find Minimum. if nums[mid] >= nums[lo]:
On [1, 2, 3, 4, 5], an array that was never rotated, it returns 5, not 1. Comparing with nums[lo] tells you mid is in the higher run, but when there's no drop there is no lower run to the right. Compare with nums[hi]: the last value is always in the run that holds the minimum.
< instead of <= when deciding which half is sorted. if nums[lo] < nums[mid]:
On [3, 1], looking for 1, it returns -1, not 1. With two values mid == lo, so the left half is a single value, which is sorted; < calls it unsorted, trusts the right half's ends, and throws the target away.
Not making mid even in Single Element.
Without mid -= 1, on [1, 1, 2, 2, 3, 4, 4] it returns 2, not 3. The pair test only means something at the start of a pair: at an odd index, "equal to the next value" compares across two pairs.
Check yourself
Quiz
1 / 5Multiple choice
[6, 7, 9, 1, 3, 4] with lo = 0, hi = 5 and mid = 2, which half is sorted?Multiple choice
Multiple choice
Multiple choice
[1, 1, 2, 2, 3, 4, 4]: at mid = 2, nums[2] = nums[3]. Where is the single value?Multiple choice
Practice problems
From easier to harder:
- Rotation Count in a Rotated Sorted Array: the index of the minimum.
- Find Minimum in Rotated Sorted Array: the first yes, compared with nums[hi].
- Search in Rotated Sorted Array: one half is always sorted.
- Search in Rotated Sorted Array II: the same, with duplicates.
- Single Element in a Sorted Array: count by pairs.
- Find Peak Element: walk uphill.
- Find in Mountain Array: peak, then two searches.
- Find a Peak Element II: the peak test in a grid.
Next: Binary Search on the Answer, where there's no array to search at all.