Binary Search on Rotation Pivot
Use binary search to locate the break point where the rotated sorted array wraps around.
0 of 3 problems solved
Binary Search on Rotation Pivot
Use binary search to locate the break point where the rotated sorted array wraps around.
- •Am I looking for the rotation break?
- •Can I compare mid with right to decide where the minimum lives?
- •Does the unsorted side contain the pivot?
Find Minimum in Rotated Sorted Array is really asking for the rotation break. In a normal sorted array, the minimum would be at the far left. Rotation pushes it somewhere inside. By comparing mid with the right boundary, you can tell whether the minimum is to the left of mid or to the right of mid.
The unsorted side is the suspicious side, because that is where the rotation break lives.
- 1Use left and right boundaries like binary search.
- 2Compare nums[mid] with nums[right].
- 3If nums[mid] is greater, the minimum is to the right of mid.
- 4If nums[mid] is smaller, the minimum is at mid or to its left.
- 5Stop when left and right meet.
Comparing mid with left can work in some variants, but using the wrong comparison rule makes the pointer moves much easier to mess up.
First Bad Version
Binary search: if mid is bad, first bad is at most mid. If mid is good, first bad is after mid. Converge until lo equals hi.
Count of Smaller Numbers After Self
Modified merge sort: while merging two halves, count how many elements from the right half land to the left of each element in the left half.