在JavaScript中旋转的排序数组中找到最小的元素
我们需要编写一个将整数数组作为唯一参数的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));输出结果
以下是控制台输出-
2