数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法学研究JavaScript程序：在已排序并旋转的数组中搜索元素
当数组按升序排序然后通过某个枢轴点旋转后，使用传统的搜索算法查找元素就变得具有挑战性。作为开发者，您需要找到一个有效的解决方案来解决这个问题。
在本文中，我们将指导您完成编写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]。我们使用数组、起始索引“0”和结束索引“arr.length - 1”调用“findPivot”函数。该函数返回枢轴点的索引，在本例中为“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]; const key = 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中的实现需要仔细考虑极端情况和实现细节，但结果是一个快速有效的搜索函数，可以处理任何大小的已排序和旋转的数组。
302 次浏览
