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中实现此算法需要仔细考虑边界情况和实施细节，但结果是一个快速高效的搜索函数，可以处理任意大小的排序和旋转数组。