# Short C# Solution Time O(log(n)) SpaceO(1) 175ms with Step Explanations

• ``````//The idea is to find out the rotating point (index newStart)
//then use newStart as starting point
//and newStart + nums.Length - 1 as ending point to do log(n) search.
public class Solution {
public int Search(int[] nums, int target) {
int begin = 0, end = nums.Length - 1;
int len = nums.Length;
int newStart;

//1. Loop to find out rotating point newStart
while (begin < end)
{
if (nums[(begin + end) / 2] < nums[len - 1])
end = (begin + end) / 2;
else if (nums[(begin + end) / 2] > nums[len - 1])
begin = (begin + end + 1) / 2;
}
newStart = nums[begin] < nums[len - 1] ? begin : end;

//2. Loop to find out target value from newStart
//    if the index is larger than nums.Length then subtract nums.Length to get the real index
begin = newStart;
end = newStart + len - 1;
while (begin < end)
{
int mid = (begin + end) / 2 > len - 1 ? ((begin + end) / 2 - len) : (begin + end) / 2;
if (nums[mid] > target)
end = (begin + end) / 2;
else if (nums[mid] < target)
begin = (begin + end + 1) / 2;
else
return mid;
}

if (end > len - 1) end -= len;
return nums[end] == target ? end : -1;

}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.