81. Search in Rotated Sorted Array II¶

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values or duplicates).

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]. 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.

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

Time complexity: \(O(log N)\)

Space complexity: \(O(1)\)

C# Solution¶

using System;

namespace Algorithm.Medium
{
  public class SearchInRotatedSortedDupArrayII
  {
    public static bool Search(int[] nums, int target)
    {
      int left = 0, right = nums.Length - 1;

      while (left <= right)
      {
        var mid = left + (right - left) / 2;
        if (nums[mid] == target) return true;

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

      }

      return false;
    }
  }
}

C# Tests¶

using Algorithm.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class SearchInRotatedSortedDupArrayIITests
  {
    [Fact]
    public void TestName()
    {
      Assert.True(SearchInRotatedSortedDupArrayII.Search(new int[] { 2, 5, 6, 0, 0, 1, 2 }, 0));
      Assert.False(SearchInRotatedSortedDupArrayII.Search(new int[] { 2, 5, 6, 0, 0, 1, 2 }, 3));
    }
  }
}

Variant: 33.search-in-rotated-sorted-array