Share my 6 lines C++


  • 0

    Best case (Array is in descending order) : O(logn)
    Worst case (Array is in ascending order): O(n)

        bool search(vector<int>& nums, int target) {
            int n = nums.size();
            if(n == 0) return false;
            int lo = n - 1;  // lo is where rotation happens
            while(lo > 0 && nums[lo-1] <= nums[lo]) lo--;
            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;
        }
    

    Same solution for 33. Search in Rotated Sorted Array Ⅰ with O(logn) complexity.

        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.