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.