在JavaScript中旋转的排序数组中找到最小的元素

Z时代
2024-01-10
分类：综合

我们需要编写一个将整数数组作为唯一参数的JavaScript函数。

首先对数组进行排序，然后旋转任意数量的元素。我们的函数应该在数组中找到最小的元素，然后返回该元素。

唯一的条件是，我们必须以小于线性时间的复杂度来做到这一点，也许要使用经过某种调整的二进制搜索算法。

例如-

如果输入数组是-

const arr = [6, 8, 12, 25, 2, 4, 5];

然后输出应为2。

示例

以下是代码-

const arr = [6, 8, 12, 25, 2, 4, 5];
const findMin = (arr = []) => {
   let temp;
   let min = 0;
   let max =arr.length- 1;
   let currentMin = Number.POSITIVE_INFINITY;
   while (min <= max) {
      temp = (min + max) >> 1;
      currentMin = Math.min(currentMin, arr[temp]);
      if (arr[min] < arr[temp] && arr[temp] <= arr[max] || arr[min] > arr[temp]) {
         max = temp - 1;
      } else if (arr[temp] === arr[min] && arr[min] === arr[max]) {
         let guessNum = arr[temp];
         while (min <= max && arr[min] === guessNum) {
            min++;
         }
      } else {
         min = temp + 1;
      }
   }
   return currentMin;
};
console.log(findMin(arr));