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


  • 0

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

Log in to reply
 

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