Recursive binary search


  • 0
    V

    The idea here is to keep dividing the array into halves. And return as soon as we see either nums[mid] > nums[mid+1] or nums[mid] < nums[mid-1]. This is not optimal as if min is on the right half, left half will go into the recursion as well. But this will work for the followup question if duplicates are allowed.

      int findMin(vector<int> &nums) {
        return helper(nums, 0, nums.size()-1);
      }
      int helper(vector<int> &nums, int start, int end) {
        if (start >= end) return nums[0];
    
        int mid = (start + end) / 2;
        if (nums[mid] > nums[mid+1]) {
          return nums[mid+1];
        }
        else if (nums[mid] < nums[mid-1]) {
          return nums[mid];
        }
        else {
          int a = helper(nums, start, mid); 
          int b = helper(nums, mid+1, end); 
          return min(a,b);
        }  
      }
    };
    

Log in to reply
 

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