Search an element in sorted rotated array

Problem: Given a sorted rotated array of distinct integers, find out the index of a given integer target in the array. If target does not exist in the array, return -1.

Approach: Using binary search.

Implementation in C#:

    public int Search(int[] nums, int target) 

    {

        int start = 0, end = nums.Length - 1;

        

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            

            if (nums[mid] == target)

            {

                return mid;

            }

            

            if (nums[start] <= nums[mid])

            {

                if (target >= nums[start] && target < nums[mid])

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            else

            {

                if (target > nums[mid] && target <= nums[end])

                {

                    start = mid + 1;

                }

                else

                {

                    end = mid - 1;

                }

            }

        }

        

        return -1;

    }

Complexity: O(logn)