[LeetCode] 33. Search in Rotated Sorted Array

 

 

 

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

 

public int Search(int[] nums, int target)
{
    return Recursive(nums, 0, nums.Length - 1, target);
}

private int Recursive(int[] nums, int start, int end, int target)
{
    int pivot = (start + end) / 2;

    if (nums[pivot] == target)
        return pivot;

    if (start == end)
        return -1;

    if (end - start == 1)
    {
        if (nums[start] == target)
            return start;
        else if (nums[end] == target)
            return end;
        else
            return -1;
    }

    if (nums[start] < nums[pivot])
    {
        if ((nums[pivot] > target) && (nums[start] <= target))
        {
            return BSearch(nums, start, pivot - 1, target);
        }
        else
        {
            return Recursive(nums, pivot + 1, end, target);
        }
    }
    else
    {
        if ((nums[pivot] < target) && (nums[end] >= target))
        {
            return BSearch(nums, pivot + 1, end, target);
        }
        else
        {
            return Recursive(nums, start, pivot - 1, target);
        }
    }
}

private int BSearch(int[] nums, int start, int end, int target)
{
    while (true)
    {
        if ((start >= end) && (nums[start] != target))
            return -1;

        int pivot = (start + end) / 2;

        if (pivot < 0)
            return -1;

        if (nums[pivot] == target)
        {
            return pivot;
        }
        else if (nums[pivot] > target)
        {
            end = pivot - 1;
        }
        else
        {
            start = pivot + 1;
        }
    }
}