# [binary search] C++ O(logn) easy to understand with comments

• First version:

``````    int search(vector<int>& nums, int target) {
if(nums.size()==0) return -1;
int i=0,j=nums.size()-1;
int mid=(i+j)/2;
//find the index of place rotated.
while(i<j){
if(nums[mid]>nums[j]) i=mid+1;
else j=mid;
mid=(i+j)/2;
}
//if target is bigger than nums[0], binary search it in 'left part'.
if(target>=nums[0]&&mid!=0){
int begin=0, end=mid-1;
int imid=(begin+end)/2;
while(begin<end){
if(nums[imid]<target) begin=imid+1;
else end=imid;
imid=(begin+end)/2;
}
if(nums[imid]==target) return imid;
else return -1;
}//else, binary search it in 'right part'.
else{
int begin=mid, end=nums.size()-1;
int imid=(begin+end)/2;
while(begin<end){
if(nums[imid]<target) begin=imid+1;
else end=imid;
imid=(begin+end)/2;
}
if(nums[imid]==target) return imid;
else return -1;
}
}
``````

EDIT(8/2/2017): Make it much cleaner and shorter.

``````    int search(vector<int>& nums, int target) {
int n = nums.size();
if(n == 0) return -1;
int lo = 0, hi = n - 1;
int mid = (lo + hi) / 2;
while(lo < hi){
if(nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
mid = (lo + hi) / 2;
}
int pos = (target >= nums[0] && lo != 0) ? lower_bound(nums.begin(), nums.begin() + lo, target) - nums.begin()
: lower_bound(nums.begin() + lo, nums.end(), target) - nums.begin();
return nums[pos] == target ? pos : -1;
}
``````

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