Binary Search
Finding a word in a paper dictionary, you open near the middle and see which side the word falls on. The other half closes for good. Binary search works the same way: one comparison rules out half of what is left.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Find Minimum in Rotated Sorted Array
or try
1–10 different numbers from -99 to 99, sorted then rotated, like 4 5 6 1 2 3.The minimum is somewhere in all 7 numbers. lo at 0, hi at 6.Step 1 of 8. Starting out. Search space index 0 to 6, all 7 numbers. The minimum is somewhere inside.
Step 1 of 8
solution.ts▶ marks the line running now
function findMin(nums: number[]): number {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return nums[lo];
}
4 · Your turn
0 of 2 problems solved
- Medium01
Find Minimum in Rotated Sorted Array
The one you just watched. Write it from memory.
- Medium02
Search in Rotated Sorted Array
Same halving, but first ask which half is sorted.