Search in rotated sorted array ii

Array Binary Search

39.8% acceptance

Jan 12, 2026

9573

1119

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4]. Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums. You must decrease the overall operation steps as much as possible.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn search(nums: Vec<i32>, target: i32) -> bool {
    let mut left = 0;
    let mut right = nums.len() as i32 - 1;
    
    while left <= right {
      let mid = left + (right - left) / 2;
      let mid_val = nums[mid as usize];
      
      if mid_val == target {
        return true;
      }
      
      // Handle duplicates
      if nums[left as usize] == mid_val && mid_val == nums[right as usize] {
        left += 1;
        right -= 1;
      } else if nums[left as usize] <= mid_val {
        // Left half is sorted
        if nums[left as usize] <= target && target < mid_val {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        // Right half is sorted
        if mid_val < target && target <= nums[right as usize] {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    
    false
  }
}