我們得到一個圍繞一個點旋轉的排序數組。我們還獲得了一個在數組中搜尋的鍵。在這個旋轉數組中搜尋元素所採用的邏輯是 -
首先，我們找到陣列的中間元素。如果密鑰存在，則我們傳回該密鑰存在於數組中。
如果鍵不在中間，我們可以查看數組的左側部分（從左到右中）是否已排序。如果已排序，則可以在左側尋找 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中文網其他相關文章！
