# Very clear C++ implementation by finding the rotation position

• ``````class Solution {
public:
int search(vector<int>& nums, int target) {
int bias=getRot(nums);
int t=binarySearch(nums, target, bias);
return nums[t]==target ? t : -1;
}

int getRot(vector<int> &nums){
int start=0, end=nums.size()-1;
while(start<end){
int mid=(start+end)/2;
if(nums[mid]>nums[end]) start=mid+1;
else end=mid;
}
return start;
}

int binarySearch(vector<int> &nums, int target, int bias){
int n=nums.size();
int start=-1, end=n-1;
while(end-start>1){
int mid=(start+end)/2;
if(nums[(mid+bias)%n] >= target) end=mid;
else start=mid;
}
return (end+bias)%n;
}
};``````

• This nice implementation can pass the duplicate cases !

``````   class Solution {
public:
int search(vector<int>& nums, int target) {
int n=nums.size();
int l=0, r=n-1;
while(l<=r){
int m=(l+r)/2;
if(nums[m]==target)  return m;
if(nums[l]<nums[m]){ /** left half is sorted **/
if(nums[l]<=target && target<nums[m])
r=m-1;
else
l=m+1;
}
else if(nums[l]>nums[m]){ /** right half is sorted **/
if(nums[m]<target && target<=nums[r]){
l=m+1;
}
else{
r=m-1;
}
}
else
l++;
}
return -1;
}
};``````

• It is better to implement the binary Search function seperately with the return index moving Rot position ...

Here is my implementation not moving the result start position , which cause WA.....

Here is the AC implementation ..

``````class Solution {
public:
int search(vector<int>& nums, int target) {
int pos = getRotPos(nums);
cout<<"pos"<<pos;
int size_nums = nums.size();
int start = 0, end = nums.size();
while(end - start > 1) {
int mid = (start + end) / 2;
if(target >= nums[(mid+pos)%size_nums])  start = mid;
else   end = mid;
}
/** bugs **/
start = (start + pos) % size_nums;
return nums[start] == target ? start : -1;
}

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

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