# Find rotate index and binary search, O(logN) 4ms C++, 156ms C#

• It's two steps to solve,

1. search rotateIndex (binary search)

2. binary search target, range is (start ~ rotateIndex-1) or (rotateIndex~end).

All of steps are O(log N) time, the solution is O(log N) time.

C++ code: (4ms)

``````int findRotateIndex(vector<int>& nums){
int left = 0;
int right = nums.size() - 1;
while (left < right){
int mid = (left + right) >> 1;
if (nums[right] < nums[mid]) left = mid + 1;
else right = mid;
}
return left;
}

int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int rotateIndex = findRotateIndex(nums);
// nums[rotateIndex] is smallest in nums
// (start -- target --) rotateIndex -- end
if (target > nums[right]) right = rotateIndex - 1;
// start -- (rotateIndex -- target -- end)
else if (target < nums[right]) left = rotateIndex;
else return right;

// binary search
while (left <= right){
int mid = (left + right) >> 1;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
``````

C# code (156ms)

``````public int Search(int[] nums, int target) {
int left = 0;
int right = nums.Length - 1;
int rotateIndex = findRotateIndex(nums);
// nums[rotateIndex] is smallest in nums
// (start -- target --) rotateIndex -- end
if (target > nums[right]) right = rotateIndex - 1;
// start -- (rotateIndex -- target -- end)
else if (target < nums[right]) left = rotateIndex;
else return right;
int result = Array.BinarySearch(nums, left, right - left + 1, target);
if(result >= 0) return result;
return -1;
}

int findRotateIndex(int[] nums){
int left = 0;
int right = nums.Length - 1;
while (left < right){
int mid = (left + right) >> 1;
if (nums[right] < nums[mid]) left = mid + 1;
else right = mid;
}
return left;
}``````

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