My short binary search C++ solution


  • 1
    D

    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])
    

    instead of

               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;
        }
    };

Log in to reply
 

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