C++程序搜索已排序旋转数组中的元素

给定一个已排序的数组，该数组围绕一个点旋转。我们还给定一个键在数组中进行搜索。在该旋转数组中搜索元素所采用的逻辑为：

  • 首先，我们找到数组的中间元素。如果键存在，则返回键存在于数组中。

  • 如果键不存在于中间位置，我们可以查看数组的左半部分（从左到中间）是否已排序。如果已排序，则可以在左半部分搜索键，否则，可以在右半部分（mid+1，right）进行搜索。

  • 如果键在中间位置未找到且左半部分未排序，则我们会对右半部分进行排序，并查看键是否存在于右半部分，或者将在数组的左侧进行搜索。

  • 否则，返回未找到。

让我们看看下面的一些输入输出场景：

假设有一个包含元素的数组。例如，2、5、7、9、11，旋转后变为 5、9、11、2、7。假设数组的键为 2。

Input: arr[] = {5, 9, 11, 2, 7}, Key=2
Output: Element "2" found at 3rd index

让我们假设另一种场景，其中键不在指定的数组中。

Input: arr[] = {10, 23, 45, 77, 84}, Key=90
Output: Element "90" not found.

算法

以下步骤是方法。

  • 找到数组的中间元素。

  • 将数组分成两部分。（mid = left + right）/ 2

  • 检查键是否为中间元素。

  • 否则，检查数组左半部分中的元素是否已排序

  • 否则，检查右半部分（mid+1，right）中的元素

  • 否则，对左半部分进行排序并检查

  • 否则，返回元素未找到。

示例

例如，假设我们有一个数组“2,3,4,5,6,7,8”，旋转后的数组为“5, 6, 7, 8, 2, 3, 4”。该数组的键为 2。

此操作的 C++ 实现如下：

#include <iostream>
#include <vector>
using namespace std;
bool solve(vector<int> arr, int left, int right, int key) {
   if (left > right) {
      return false;
   }
   int mid = (left + right)/2;
   if (arr[mid] == key) {
      return true;
   }
   if (arr[left] <= arr[mid]) {
      if (key >= arr[left] && key <= arr[mid]) {
         return solve(arr, left, mid-1, key);
      }
      return solve(arr, mid+1, right, key);
   }
   if (key >= arr[mid] && key <= arr[right])
      return solve(arr, mid+1, right, key);
   return solve(arr, left, mid-1, key);
}
int main() {
   vector<int> arr = {5, 6, 7, 8, 2, 3, 4};
   int key = 2;
   if(solve(arr, 0, arr.size()-1, key)) cout << key << " is present";
      else cout << key << " is not present";
   return 0;
}

输出

2 is present

结论

解决此问题的另一种方法是找出枢轴点或数组围绕其旋转的索引，然后对该侧进行二分查找。我们的方法只需要一次二分查找即可解决问题。每当我们看到搜索和已排序的数组时，都应该将二分查找作为一种方法。

更新于： 2022年8月10日

829 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告