Original link: leetcode-cn.com/problems/fi…

Answer:

  1. 2. According to the passage, it can be divided into two cases:

    • nums[mid] < nums[right]

Use cases:,6,1,2,3,4 [5]

Use cases:,13,15,17 [11]

Use cases:,1,2 [3]

* nums[mid] > nums[right]
Copy the code

Use cases:,4,5,6,1,2 [3]

Use cases: [2, 1]

  1. This problem does not have a target value to look up, so that when the left and right Pointers meet, they both point to the minimum value. So the cycle continues underleft < right.
/ * * *@param {number[]} nums
 * @return {number}* /
var findMin = function (nums) {
  let left = 0; // binary search left boundary
  let right = nums.length - 1; // Binary search the right boundary

  // Since there is no target value to determine, the loop needs to exit before left equals right
  // When two Pointers meet, the result is found
  while (left < right) {
    // Take the midpoint of two Pointers
    const mid = (left + right) >> 1;

    // if nums[mid] < nums[right], the rotation point is in the left half
    if (nums[mid] < nums[right]) {
      // Since mid is always rounded downward, mid=left in the limit case when only two values are left.
      // And there is no judgment that the midpoint is equal to the target value, so the midpoint must always be included in the interval
      right = mid;
    }
    // if nums[mid] > nums[right], the rotation point is in the right half
    else if (nums[mid] > nums[right]) {
      // Left can be equal to mid+1
      left = mid + 1; }}// When exiting the loop, the left and right Pointers must meet and point to the minimum value
  return nums[left];
};
Copy the code