在一個已排序且旋轉的陣列中搜尋元素的C++程序

我們得到一個圍繞一個點旋轉的排序數組。我們還獲得了一個在數組中搜尋的鍵。在這個旋轉數組中搜尋元素所採用的邏輯是 -

• 首先，我們找到陣列的中間元素。如果密鑰存在，則我們傳回該密鑰存在於數組中。

• 如果鍵不在中間，我們可以查看數組的左側部分（從左到右中）是否已排序。如果已排序，則可以在左側尋找 key，否則可以在右側（mid 1, right）找到

• #如果中間沒有找到key，且左邊部分沒有排序，那麼我們會對右邊部分進行排序，然後我們可以看看右邊部分是否存在該key，或者我們會在右邊部分進行搜尋數組的左側

• 否則我們回傳找不到。

讓我們看看下面的一些輸入輸出場景 -

想像有一個由其中的元素組成的陣列。例如，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.

演算法

以下步驟是實作方法。

• 找出陣列的中間元素。

• 將陣列分成兩部分。 ( 中 = 左 右 ) / 2

• 檢查key是否為中間元素。

• Else if ，檢查數組左側的元素並且它已排序

• else if，檢查右側元素（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

結論

解決此問題的另一種方法是找出陣列旋轉的樞軸點或索引，然後對邊進行二分搜尋。我們的方法只需要 1 次二分搜尋即可解決問題。每當我們看到搜尋和排序數組時，我們都應該將二分搜尋作為搜尋方法之一。

以上是在一個已排序且旋轉的陣列中搜尋元素的C++程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！