寻找旋转数组中的最小数字

// 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
// 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
// 例如，数组[3，4，5，1，2]为[1，2，3，4，5]的一个旋转，该数组的最小值为1。
export default class FindWhirlingArrayMinVal {
  private leftPointer;
  private rightPointer;
  private middleIndex;
  constructor() {
    this.leftPointer = 0;
    this.rightPointer = 0;
    this.middleIndex = 0;
  }
  public getMinValue(incrementArray: Array<number>): number {
    this.rightPointer = incrementArray.length - 1;
    // 第一个元素小于最后一个元素，证明数组是排好序的
    if (incrementArray[this.leftPointer] < incrementArray[this.rightPointer]) {
      // 其最小值为第一个元素
      return incrementArray[this.leftPointer];
    }
    while (
      incrementArray[this.leftPointer] >= incrementArray[this.rightPointer]
    ) {
      // 循环终止条件: 右指针与左指针相邻，最小值为右指针所指向的值
      if (this.rightPointer - this.leftPointer === 1) {
        this.middleIndex = this.rightPointer;
        break;
      }
      // 求中间值
      this.middleIndex = Math.floor((this.leftPointer + this.rightPointer) / 2);
      // 左指针指向的值与右指针指向的值相同且中间元素也与之相同
      // 则无法使用二分查找，需要顺序查找
      if (
        incrementArray[this.leftPointer] ===
          incrementArray[this.rightPointer] &&
        incrementArray[this.middleIndex] === incrementArray[this.leftPointer]
      ) {
        // 按顺序查找
        let minValue = incrementArray[0];
        for (let i = 0; i < incrementArray.length; i++) {
          if (incrementArray[i] < minValue) {
            minValue = incrementArray[i];
          }
        }
        return minValue;
      }
      if (
        incrementArray[this.middleIndex] >= incrementArray[this.leftPointer]
      ) {
        // 中间值大于等于左指针指向的值
        // 移动左指针至中间值位置
        this.leftPointer = this.middleIndex;
      } else if (
        incrementArray[this.middleIndex] <= incrementArray[this.rightPointer]
      ) {
        // 中间值小于等于右指针指向的值
        // 移动右指针至中间值位置
        this.rightPointer = this.middleIndex;
      }
    }
    // 循环结束，返回最小值
    return incrementArray[this.middleIndex];
  }
}

const findWhirlingArrayMinVal = new FindWhirlingArrayMinVal();
let whirlArray = [3, 4, 5, 1, 2];
console.log(
  `旋转数组[${whirlArray}]的最小值为`,
  findWhirlingArrayMinVal.getMinValue(whirlArray)
);
whirlArray = [1, 0, 1, 1, 1];
console.log(
  `旋转数组[${whirlArray}]的最小值为`,
  findWhirlingArrayMinVal.getMinValue(whirlArray)
);
whirlArray = [1, 1, 1, 0, 1];
console.log(
  `旋转数组[${whirlArray}]的最小值为`,
  findWhirlingArrayMinVal.getMinValue(whirlArray)
);