# 在經過排序和旋轉的數組中搜索元素 > 原文： [https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/](https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/) 通過[二分搜索](https://www.geeksforgeeks.org/binary-search/)可以在`O(log n)`時間找到排序數組中的元素。 但是，假設我們在您事先不知道的某個樞軸處旋轉一個升序排序的數組。 因此，例如`1 2 3 4 5`可能變成`3 4 5 1 2`。設計一種在`O(log n)`時間內在旋轉數組中查找元素的方法。  ``` Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}; key = 3 Output : Found at index 8 Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}; key = 30 Output : Not found Input : arr[] = {30, 40, 50, 10, 20} key = 10 Output : Found at index 3 ``` **此處提供的所有解決方案均假定數組中的所有元素都是不同的。** 這個想法是找到樞軸點，將數組分為兩個子數組，然后調用二分搜索。 查找樞軸的主要思想是–對于排序（按遞增順序）和樞軸化的數組，樞軸元素是唯一一個其下一個元素小于它的元素。 使用上述標準和二分搜索方法，我們可以在`O(logn)`時間中獲取樞軸元素 ``` Input arr[] = {3, 4, 5, 1, 2} Element to Search = 1 1) Find out pivot point and divide the array in two sub-arrays. (pivot = 2) /*Index of 5*/ 2) Now call binary search for one of the two sub-arrays. (a) If element is greater than 0th element then search in left array (b) Else Search in right array (1 will go in else as 1 < 0th element(3)) 3) If element is found in selected sub-array then return index Else return -1. ``` 下面是上述方法的實現： ## C++ ```cpp /* C++ Program to search an element ???in a sorted and pivoted array*/ #include <bits/stdc++.h> using namespace std; /* Standard Binary Search function*/ int binarySearch(int arr[], int low,? ??????????????????int high, int key) { ??if (high < low) ????return -1; ??int mid = (low + high)/2; /*low + (high - low)/2;*/ ??if (key == arr[mid]) ????return mid; ??if (key > arr[mid]) ????return binarySearch(arr, (mid + 1), high, key); ??// else ????return binarySearch(arr, low, (mid -1), key); } /* Function to get pivot. For array 3, 4, 5, 6, 1, 2 ???it returns 3 (index of 6) */ int findPivot(int arr[], int low, int high) { ??// base cases ??if (high < low) return -1; ??if (high == low) return low; ???int mid = (low + high)/2; /*low + (high - low)/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); } /* Searches an element key in a pivoted ???sorted array arr[] of size n */ int pivotedBinarySearch(int arr[], int n, int key) { ??int pivot = findPivot(arr, 0, n-1); ??// If we didn't find a pivot,? ??// then array is not rotated at all ??if (pivot == -1) ????return binarySearch(arr, 0, n-1, key); ??// If we found a pivot, then first compare with pivot ??// and then search in two subarrays around pivot ??if (arr[pivot] == key) ????return pivot; ??if (arr[0] <= key) ????return binarySearch(arr, 0, pivot-1, key); ????return binarySearch(arr, pivot+1, n-1, key); } /* Driver program to check above functions */ int main() { ??// Let us search 3 in below array ??int arr1[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}; ??int n = sizeof(arr1)/sizeof(arr1[0]); ??int key = 3; ??// Function calling ??cout << "Index of the element is : " <<? ???????????pivotedBinarySearch(arr1, n, key); ??return 0; } ```