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)
