Binary Search on Rotated Array
Find the sorted half first, then keep only the half that could still contain the target.
0 of 3 problems solved
Binary Search on Rotated Array
Find the sorted half first, then keep only the half that could still contain the target.
- •Is one half of the rotated array still sorted?
- •Can I detect which side is normal at mid?
- •Can that sorted side tell me where the target cannot be?
A rotated sorted array looks messy, but it still hides order. At any moment, one side of the array is properly sorted. Your job is to detect which side is normal, then check whether the target could live there. If not, throw that side away and search the other half. It is binary search wearing a slightly annoying hat.
Even after rotation, one half is always sorted enough to give you information.
- 1Find mid as usual.
- 2Check whether the left half or right half is sorted.
- 3Ask whether the target lies inside that sorted half's range.
- 4Keep the half that could still contain the target and discard the other.
Treating the array like a normal sorted array misses the rotation clue. You have to detect which half is sorted before choosing a side.
Search Insert Position
Standard binary search. Return left instead of -1 when the target is missing — that is exactly where the target would be inserted.
Find Minimum in Rotated Sorted Array II
Same as the version without duplicates but when mid equals high you can only safely shrink by one (high--) instead of halving the range.