# My short binary search C++ solution

• The idea is to do binary search. Since due to the shift, the two halfs may not be both in order but at least one of them is in order, so always check the in-order half and see if the target is in the range of that half.
One mistake I made is I used

``````                    if(nums[left]<nums[mid])
``````

``````           if(nums[left]<=nums[mid])
``````

That causes an error in the case [3,1] since when the length is 2, mid is equal to left

``````class Solution {
public:
int search(vector<int>& nums, int target) {
int res, left =0, right= nums.size()-1, mid;
while(left<=right)
{
mid= (left+right)/2;
if(nums[mid] == target) return mid;
if(nums[left]<=nums[mid])
{// if the first half is in-order, <= since mid may be equal to left when there are only two elements
if(target>=nums[left] && target < nums[mid] ) right = mid -1;  // if target is in the range of the first half
else left = mid + 1;
}
else
{// if the second half is in order
if(target > nums[mid] && target <= nums[right] ) left = mid + 1; // target is in the range of the second half
else right = mid - 1;
}
}
return -1;
}
};
``````

I revised the above version to make it more neat

``````class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0, right=nums.size()-1, mid;
while(left<=right)
{
mid = (left+right)/2;
if(target==nums[mid]) return mid;
if( (nums[left]<= target && target < nums[mid]) || (nums[mid]< nums[right] && (nums[mid]>target || nums[right]<target)) )  right = mid-1; // if it the first half is in order and target is in that range or the second half is in order and target is not in the second half
else left = mid+1;
}
return -1;
}
};``````

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