Search in Rotated Sorted Array in c#

Programming C#
1

Searching in a rotated sorted array is a common problem in coding interviews and can be efficiently solved using a modified binary search algorithm. A rotated sorted array is one that has been sorted and then rotated at some pivot point. For example, the array [4, 5, 6, 7, 0, 1, 2] is a rotated version of the sorted array [0, 1, 2, 4, 5, 6, 7].

Problem Statement

Given a rotated sorted array and a target value, you need to determine if the target exists in the array and return its index if it does. If the target does not exist, return -1.

Approach

  1. Identify the Pivot: The pivot is the point where the rotation has occurred. This can be found using a modified binary search.
  2. Determine Which Side to Search: Once you have the pivot, you can determine which side of the array to search based on the target’s value.
  3. Perform Binary Search: Depending on which half the target may exist in, perform a standard binary search on that half.

C# Implementation

Here’s how you can implement this approach in C#:

public class Solution
{
    public int Search(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            // Check if mid is the target
            if (nums[mid] == target)
                return mid;

            // Determine which side is sorted
            if (nums[left] <= nums[mid]) // Left side is sorted
            {
                if (nums[left] <= target && target < nums[mid]) // Target in left side
                    right = mid - 1;
                else // Target in right side
                    left = mid + 1;
            }
            else // Right side is sorted
            {
                if (nums[mid] < target && target <= nums[right]) // Target in right side
                    left = mid + 1;
                else // Target in left side
                    right = mid - 1;
            }
        }

        return -1; // Target not found
    }
}

Explanation of the Code

  1. Initialization: We initialize two pointers, left and right, to represent the bounds of our search space.
  2. Binary Search Loop: The while loop continues until the search space is empty (left exceeds right).
  3. Mid Calculation: We calculate the midpoint to check if it equals the target.
  4. Identifying Sorted Halves:
    • If the left half is sorted (nums[left] <= nums[mid]), we check if the target is within this range. If it is, we adjust our search space to the left half; otherwise, we search the right half.
    • If the right half is sorted, we do the opposite check.
  5. Return Statement: If we exit the loop without finding the target, we return -1.

Complexity

  • Time Complexity: O(log n) due to the binary search.
  • Space Complexity: O(1) since we’re using a constant amount of space.

This method effectively handles the search in a rotated sorted array, leveraging the properties of both binary search and the sorted nature of the array.