33 Search in Rotated Sorted Array¶

There is an integer array nums sorted in ascending order (with distinct values).

Prior to 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,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

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

Space complexity: \(O(1)\)

C# Solution¶

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class SearchInRotatedSortedUniqueArray
  {
    public static int 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 mid;

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

      }

      return -1;
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class SearchInRotatedSortedUniqueArrayTests
  {
    [Fact]
    public void TestName()
    {
      Assert.Equal(4, SearchInRotatedSortedUniqueArray.Search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 0));
      Assert.Equal(-1, SearchInRotatedSortedUniqueArray.Search(new int[] { 4, 5, 6, 7, 0, 1, 2 }, 3));
      Assert.Equal(-1, SearchInRotatedSortedUniqueArray.Search(new int[] { 1 }, 0));
    }
  }
}

Variant: 81.search-in-rotated-sorted-array-ii