Search in rotated sorted array

Array Binary Search

44.1% acceptance

Jan 12, 2026

29765

1803

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    
    while left <= right {
      let mid = left + (right - left) / 2;
      
      if nums[mid] == target {
        return mid as i32;
      }
      
      // Determine which half is sorted
      if nums[left] <= nums[mid] {
        // Left half is sorted
        if nums[left] <= target && target < nums[mid] {
          // Target is in the sorted left half
          if mid == 0 {
            break;
          }
          right = mid - 1;
        } else {
          // Target is in the right half
          left = mid + 1;
        }
      } else {
        // Right half is sorted
        if nums[mid] < target && target <= nums[right] {
          // Target is in the sorted right half
          left = mid + 1;
        } else {
          // Target is in the left half
          if mid == 0 {
            break;
          }
          right = mid - 1;
        }
      }
    }
    
    -1
  }
}