10 lines simple and concise C++ solution with detailed explanation and thought process


  • 3

    THOUGHT:

    We know that a normal sorted array has an increasing trend from beginning to the end, but a rotated array may have some point that break the trend. For example, 4 5 6 7 1 2 3, if you look at 4 5 6 7 and 1 2 3 separately, you see two increasing sub-array, and the observation is:

    The rightmost number of the second sub-array is smaller than the leftmost number of the first sub-array if there exists and rotated position

    So every time, when we get the mid position, compare to nums[r] to see if the rotated position is on the right half:

    1. If nums[mid] > nums[r], which not follows the increasing trend, so we know that the rotated position (smallest number in this array) is on the right side of mid position, so please have some thought here, what kind of numbers will be on the right side? It should be either numbers greater than nums[mid] or less than or equal to nums[r]. So check if target is in this range, if yes, we pick the right side by updating index l to mid + 1, otherwise, we pick the left side. Giving an example here,
      4 5 6 7 8 1 2 3. So here, nums[mid] = 7, nums[r] = 3, you'll see numbers greater than 7 (number 8) and numbers <= nums[r] (number 1, 2, 3) are on the right side of mid.

    2. If nums[mid] < nums[r], we know that the numbers on the right side are in pure increasing order now, and if target falls into this range, we pick the right side, otherwise, we pick the left side.

    Hope this makes sense.

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int l = 0, r = nums.size() - 1;
            
            while(l <= r){ 
                int mid = l + (r - l) / 2;
                
                if(nums[mid] == target) return mid;
                if(nums[mid] > nums[r]){
                    if(target > nums[mid] || target <= nums[r]) l = mid + 1;   // condition for pick right side
                    else r = mid - 1;    // else, pick left side
                }else{
                    if(target <= nums[r] && target > nums[mid]) l = mid + 1;  // condition for pick right side
                    else r = mid - 1;     // else, pick left side
                } 
            }
            
            return -1;
        }
    };

  • 0
    Q

    Shouldn't this || be && ? Just like the corresponding one.

    if(target > nums[mid] || target <= nums[r]) l = mid + 1;


Log in to reply
 

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