C++ 4ms binary search with some comments


  • 4
    P
    // Lets represent rotated array 4567890123 as:
    //             9
    //           8    <--- top middle
    //         7         
    //       6
    //     5
    //   4
    //  -0-1-2-3-4-5-6-7-8-9- [index] in array  
    //                     3
    //                   2
    //                 1    <--- bottom middle
    //               0
    // When you do binary search your middle index is either on the "top" or "bottom" index
    // when l == 0 and r == 9 then mid == 4, mid_number == nums[mid] == 8 
    // I call it "top middle", since it always > than both nums[l] and nums[r] (4 < 8 > 3)
    // so the min value is on the right side of it
    // when l == 4 and r == 9 then mid == 7, mid_number == nums[mid] == 1 
    // I call it "bottom middle" since it always < than both nums[l] and nums[r] (8 > 1 < 3)
    // so the min value is somewhere on the left side of it
    int findMin(vector<int>& nums) 
    {
       int l = 0, r = nums.size() - 1;
       while(r - l > 1)
       {
           int mid = (l + r) / 2;
           if(nums[l] < nums[mid] && nums[mid] > nums[r])
           {
               l = mid; // top middle, min value is somewhere on the right
           }
           else
           {
               r = mid; // bottom middle, min value is somewhere on the left
           }
       }
       
       return min(nums[l], nums[r]);
    }

Log in to reply
 

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