Very clear C++ implementation by finding the rotation position


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

  • 0

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

  • 0
    2

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

Log in to reply
 

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