Search in Rotated Sorted Array II

LeetCode 81 | Difficulty: Medium

Medium

Problem Description

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.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

• 1 <= nums.length <= 5000

• -10^4 <= nums[i] <= 10^4

• nums is guaranteed to be rotated at some pivot.

• -10^4 <= target <= 10^4

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 80 ms)

Metric	Value
Runtime	80 ms
Memory	40.8 MB
Date	2021-11-24

Solution

public class Solution {
    public bool Search(int[] nums, int target) {
        int l = 0, r = nums.Length - 1;
	while (l <= r)
	{
		int mid = l + (r - l) / 2;
		if (target == nums[mid])
		{
			return true;
		}
		
		if(nums[l] == nums[mid] && nums[mid] == nums[r])
		{
			l++;
			r--;
			continue;
		}

		if (nums[l] <= nums[mid])
		{
			if (target >= nums[l] && target < nums[mid])
			{
				r = mid - 1;
			}
			else
			{
				l = mid + 1;
			}
		}
		else
		{
			if (target > nums[mid] && target <= nums[r])
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
			}
		}
		

	}
	return false;
    }
}

📜 2 more C# submission(s)

Submission (2021-11-24) — 92 ms, 40.9 MB

public class Solution {
    public bool Search(int[] nums, int target) {
        var arrLen = nums.Length;
        if(arrLen == 0)
            return false;
        
        var low = 0;
        var high = arrLen - 1;
        while(low <= high)
        {
            var mid = low + (high - low)/2;
            if(nums[mid] == target)
                return true;
            
			// Decrease search space
            if(nums[low] == nums[mid] && nums[mid] == nums[high])
            {
                ++low;
                --high;
                continue;
            }
            
            // First half
            if(nums[low] <= nums[mid])
            {
                if(nums[mid] > target && target >= nums[low])
                {
                    high = mid-1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            else
            {
                // second half
                if(target > nums[mid] && target <= nums[high])
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid - 1;
                }
            }
        }
            
        return false;
    }
}

Submission (2018-07-04) — 112 ms, N/A

public class Solution {
    public bool Search(int[] nums, int target)
{
	if(nums.Length<1) return false;
	int lo = 0, hi = nums.Length-1;
	while(lo<=hi)
	{
		int mid = lo + (hi-lo)/2;
		if(nums[mid] == target) return true;
		else if(nums[mid]>nums[hi])
		{
			if(target>=nums[lo] && target<nums[mid])
			{
				hi = mid;
			}
			else lo=mid+1;
		}
		else if(nums[mid]<nums[hi])
		{
			if(target > nums[mid] && target <= nums[hi])
			{
				lo = mid+1;
			}
			else hi = mid;
		}
		else hi--;
	}
	return nums[lo]==target;

}
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.