Smallest element in rotated sorted array

思路

一个排好序但被旋转的数组，最小值一定是旋转点。

例如：

原数组

[1, 2, 3, 4, 5]

旋转后可能变成

[4, 5, 1, 2, 3]

其中最小值是 1，它也是排序断点的位置。

利用二分查找来定位最小值即可。

算法步骤

1. 令 left = 0，right = n - 1，中点 mid = Math.floor((left + right) / 2)

2. 判断 numbers[mid] 与 numbers[right]：

   • numbers[mid] > numbers[right] 说明最小值在 mid 右侧，令 left = mid + 1
   • numbers[mid] < numbers[right] 说明最小值在 mid 或左侧，令 right = mid

3. 当 left === right 时，即为最小值位置。

代码实现

function findMin(numbers: number[]): number {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (numbers[mid] > numbers[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return numbers[left];
}