当数组按升序排序，然后按某个枢轴点旋转时，使用传统搜索算法搜索元素变得具有挑战性。作为开发人员，您需要找到解决此问题的有效解决方案。
在本文中，我们将指导您完成编写 JavaScript 程序以在已排序和旋转的数组中搜索元素的过程。我们将解释底层逻辑，并为您提供实施该计划的分步方法。
在开始之前，让我们先了解一下问题陈述。我们有一个已排序的数组，已旋转了一些未知的量。
例如，原始数组可能是[1, 2, 3, 4, 5, 6]，但旋转后变成了[4, 5, 6, 1, 2, 3]。现在，我们需要在旋转数组中搜索特定元素。
我们需要做的第一件事是找到枢轴点，即数组旋转的点。一旦找到枢轴点，我们就可以对两个子数组执行二分查找来找到我们要查找的元素。
为了找到枢轴点，我们可以使用修改后的二分搜索算法。我们首先找到数组的中间元素并将其与第一个元素进行比较。如果中间元素大于第一个元素，我们就知道枢轴点位于数组的后半部分。如果中间元素小于第一个元素，我们就知道枢轴点位于数组的前半部分。
我们继续这个过程，直到找到枢轴点。一旦找到枢轴点，我们就可以将数组分成两个子数组并对它们执行二分查找。
输入
Array: [4, 5, 6, 1, 2, 3]
输出
Pivot index: 2
请注意，数据透视索引可能会根据输入数组的不同而有所不同。
找到枢轴点。
在下面的 JavaScript 程序中，我们有一个已排序和旋转的数组 [4, 5, 6, 1, 2, 3]。我们使用数组调用“findPivot 函数”，起始索引为“0”，结束索引为“arr.length - 1”。该函数返回枢轴点的索引，在本例中为“2”。
function findPivot(arr, low, high) {
if (high < low) return -1;
if (high === low) return low;
const mid = Math.floor((low + high) / 2);
if (mid < high && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > low && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
if (arr[low] >= arr[mid]) {
return findPivot(arr, low, mid - 1);
}
return findPivot(arr, mid + 1, high);
}
// Example usage
const arr = [4, 5, 6, 1, 2, 3];
console.log("Array: " + JSON.stringify(arr));
const pivotIndex = findPivot(arr, 0, arr.length - 1);
console.log("Pivot index:", pivotIndex);
一旦找到枢轴点，我们就可以对两个子数组执行二分搜索来找到我们要查找的元素。我们需要两个单独的二分搜索函数：一个用于第一个子数组，一个用于第二个子数组。
输入 - const arr = [1, 2, 3, 4, 5, 6, 7];常量键 = 4;
输出− 3
在此示例中，二分查找函数返回索引“3”，它对应于数组中的值“4”。
下面的程序使用二分搜索算法在数组中搜索键。它首先通过比较起始索引和结束索引来检查键是否存在于数组中。如果密钥不存在，则返回-1。如果存在，它会计算中间索引并将该索引处的值与键进行比较。如果值等于键，则返回中间索引。如果值小于键，则继续在数组的右半部分搜索，如果大于键，则在数组的左半部分搜索，直到找到该键或数组中不存在该键为止.
function binarySearch(arr, low, high, key) {
if (high < low) return -1;
const mid = Math.floor((low + high) / 2);
if (arr[mid] === key) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(arr, low, mid - 1, key);
} else {
return binarySearch(arr, mid + 1, high, key);
}
}
const arr = [1, 2, 3, 4, 5, 6, 7];
const key = 4;
const result = binarySearch(arr, 0, arr.length - 1, key);
console.log("The searched element found at index ", result);
可以使用修改后的二分搜索算法来搜索已排序和旋转的数组中的元素。该算法的关键是识别数组中的枢轴点，然后将数组划分为两个已排序的子数组。然后对适当的子数组执行二分搜索以定位键。在 JavaScript 中实现该算法需要仔细考虑边缘情况和实现细节，但结果是一个快速高效的搜索函数，可以处理任何大小的排序和旋转数组。
