A complete visual walkthrough of the modified binary search — understanding which half is sorted and where the target hides.
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Example 3:
Input: nums = [1], target = 0 Output: -1
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums are unique.nums is an ascending array that is possibly rotated.-104 <= target <= 104The naive approach ignores the sorted structure entirely: just scan every element until you find the target.
for (int i = 0; i < nums.length; i++) { if (nums[i] == target) return i; } return -1;
for i, v := range nums { if v == target { return i } } return -1
for i in range(len(nums)): if nums[i] == target: return i return -1
for (i, &v) in nums.iter().enumerate() { if v == target { return i as i32; } } -1
for (let i = 0; i < nums.length; i++) { if (nums[i] === target) return i; } return -1;
This is O(n) — it works but ignores the fact that the array is nearly sorted. The problem explicitly requires O(log n), which means binary search.
Key question: Standard binary search needs a fully sorted array. A rotated array has a "break point." How can we still use binary search? The trick is recognizing that at least one half is always sorted.
When you pick the midpoint of a rotated sorted array, the rotation break can only be in one half. The other half is guaranteed to be perfectly sorted.
Array [4, 5, 6, 7, 0, 1, 2] — rotated at index 4. The values form a "broken staircase":
The left segment [4,5,6,7] is sorted. The right segment [0,1,2] is also sorted. The break is between them.
[nums[lo], nums[mid]). If yes, search left. Otherwise search right.(nums[mid], nums[hi]]. If yes, search right. Otherwise search left.Why does this work? In the sorted half, we can definitively say whether the target is there (it must be within its range). If the target is not in the sorted half, it must be in the other half — the one containing the rotation break.
Let's trace nums = [4,5,6,7,0,1,2], target = 0 step by step.
| Iter | lo | hi | mid | nums[mid] | Sorted Half | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | Left [4,5,6,7] | target=0 not in [4,7] → lo = 4 |
| 2 | 4 | 6 | 5 | 1 | Right [1,2] | target=0 not in (1,2] → hi = 4 |
| 3 | 4 | 4 | 4 | 0 | — | Found! return 4 |
Visual state at each iteration:
nums[lo] <= nums[mid] check handles both correctly.class Solution { public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // Found the target if (nums[mid] == target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted if (target >= nums[lo] && target < nums[mid]) hi = mid - 1; // target is in sorted left half else lo = mid + 1; // target is in right half } else { // Right half [mid..hi] is sorted if (target > nums[mid] && target <= nums[hi]) lo = mid + 1; // target is in sorted right half else hi = mid - 1; // target is in left half } } return -1; // target not found } }
func search(nums []int, target int) int { lo, hi := 0, len(nums)-1 for lo <= hi { mid := lo + (hi-lo)/2 // Found the target if nums[mid] == target { return mid } if nums[lo] <= nums[mid] { // Left half [lo..mid] is sorted if target >= nums[lo] && target < nums[mid] { hi = mid - 1 // target is in sorted left half } else { lo = mid + 1 // target is in right half } } else { // Right half [mid..hi] is sorted if target > nums[mid] && target <= nums[hi] { lo = mid + 1 // target is in sorted right half } else { hi = mid - 1 // target is in left half } } } return -1 // target not found }
def search(nums: list[int], target: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 # Found the target if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # Left half [lo..mid] is sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 # target is in sorted left half else: lo = mid + 1 # target is in right half else: # Right half [mid..hi] is sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 # target is in sorted right half else: hi = mid - 1 # target is in left half return -1 # target not found
impl Solution { pub fn search(nums: Vec<i32>, target: i32) -> i32 { let (mut lo, mut hi) = (0i32, nums.len() as i32 - 1); while lo <= hi { let mid = lo + (hi - lo) / 2; // Found the target if nums[mid as usize] == target { return mid; } if nums[lo as usize] <= nums[mid as usize] { // Left half [lo..mid] is sorted if target >= nums[lo as usize] && target < nums[mid as usize] { hi = mid - 1; // target is in sorted left half } else { lo = mid + 1; // target is in right half } } else { // Right half [mid..hi] is sorted if target > nums[mid as usize] && target <= nums[hi as usize] { lo = mid + 1; // target is in sorted right half } else { hi = mid - 1; // target is in left half } } } -1 // target not found } }
function search(nums: number[], target: number): number { let lo = 0, hi = nums.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); // Found the target if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted if (target >= nums[lo] && target < nums[mid]) hi = mid - 1; // target is in sorted left half else lo = mid + 1; // target is in right half } else { // Right half [mid..hi] is sorted if (target > nums[mid] && target <= nums[hi]) lo = mid + 1; // target is in sorted right half else hi = mid - 1; // target is in left half } } return -1; // target not found }
Enter a rotated sorted array and a target value. Step through to see which half is identified as sorted and how pointers move.
Each iteration halves the search space, just like standard binary search. We perform at most log2(n) comparisons. Only a constant number of pointer variables are used -- no extra data structures needed, giving O(1) space.
A single for-loop walks through all n elements comparing each to the target. In the worst case (target absent or at the end), every element is visited -- O(n). No auxiliary data structures are used, just one loop index variable.
Modified binary search halves the search space each iteration. At each midpoint, one half is guaranteed sorted; we check if the target falls within that sorted range to decide which half to discard. This yields at most log2(n) iterations. Only three pointer variables (lo, hi, mid) are used.
At each step, one half is guaranteed sorted -- compare the target with that half's bounds to decide direction. The rotation does not hurt us. Even though the array is not fully sorted, the property that one half is always sorted gives us enough information to discard the other half, preserving the O(log n) guarantee.
Review these before coding to avoid predictable interview regressions.
Wrong move: Using incorrect boundary checks causes binary search to choose the wrong half.
Usually fails on: Pivot-near-ends arrays route search away from the target.
Fix: First detect whether left half is sorted (`nums[lo] <= nums[mid]`) or right half is sorted.
Wrong move: Mixing `<` and `<=` in range checks drops valid targets at boundaries.
Usually fails on: Target at `lo`, `mid`, or `hi` is skipped.
Fix: Use consistent inclusive/exclusive checks and shrink bounds by `mid ± 1`.
Wrong move: Switching to scan after uncertain branch defeats logarithmic complexity.
Usually fails on: Large inputs time out due to hidden O(n) path.
Fix: Maintain binary-search invariant each iteration; never scan.