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 次檢視

啟動您的 職業生涯

透過完成課程獲得認證

開始
廣告

© . All rights reserved.