# 在經過排序和旋轉的數組中找到最小元素 > 原文： [https://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/](https://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/) 將已排序的數組旋轉到某個未知點，在其中找到最小的元素。 以下解決方案假定所有元素都是不同的。 **示例**： ``` Input: {5, 6, 1, 2, 3, 4} Output: 1 Input: {1, 2, 3, 4} Output: 1 Input: {2, 1} Output: 1 ``` 一個簡單的解決方案是遍歷整個數組并找到最小值。 該解決方案需要`O(n)`時間。 我們可以使用二分搜索在`O(Logn)`中進行操作。 如果我們仔細看一下上面的示例，我們可以很容易地找出以下模式： * 最小元素是前一個大于它的唯一元素。 如果沒有先前的元素元素，則不會旋轉（第一個元素最少）。 我們通過將此條件與第（`mid-1`）個和第（`mid + 1`）個元素進行比較來檢查此條件。 * 如果最小元素不在中間（既不是`mid`也不是`mid+1`），則最小元素位于左半部分或右半部分。 1. 如果中間元素小于最后一個元素，則最小元素位于左半部分 2. 其他最小元素位于右半部分。 強烈建議您先嘗試一下，然后再查看以下實現。 ## C++ ```cpp // C++ program to find minimum? // element in a sorted and rotated array? #include <bits/stdc++.h> using namespace std; int findMin(int arr[], int low, int high)? {? ????// This condition is needed to? ????// handle the case when array is not? ????// rotated at all? ????if (high < low) return arr[0];? ????// If there is only one element left? ????if (high == low) return arr[low];? ????// Find mid? ????int mid = low + (high - low)/2; /*(low + high)/2;*/ ????// Check if element (mid+1) is minimum element. Consider? ????// the cases like {3, 4, 5, 1, 2}? ????if (mid < high && arr[mid + 1] < arr[mid])? ????return arr[mid + 1];? ????// Check if mid itself is minimum element? ????if (mid > low && arr[mid] < arr[mid - 1])? ????return arr[mid];? ????// Decide whether we need to go to left half or right half? ????if (arr[high] > arr[mid])? ????return findMin(arr, low, mid - 1);? ????return findMin(arr, mid + 1, high);? }? // Driver program to test above functions? int main()? {? ????int arr1[] = {5, 6, 1, 2, 3, 4};? ????int n1 = sizeof(arr1)/sizeof(arr1[0]);? ????cout << "The minimum element is " << findMin(arr1, 0, n1-1) << endl;? ????int arr2[] = {1, 2, 3, 4};? ????int n2 = sizeof(arr2)/sizeof(arr2[0]);? ????cout << "The minimum element is " << findMin(arr2, 0, n2-1) << endl;? ????int arr3[] = {1};? ????int n3 = sizeof(arr3)/sizeof(arr3[0]);? ????cout<<"The minimum element is "<<findMin(arr3, 0, n3-1)<<endl;? ????int arr4[] = {1, 2};? ????int n4 = sizeof(arr4)/sizeof(arr4[0]);? ????cout<<"The minimum element is "<<findMin(arr4, 0, n4-1)<<endl;? ????int arr5[] = {2, 1};? ????int n5 = sizeof(arr5)/sizeof(arr5[0]);? ????cout<<"The minimum element is "<<findMin(arr5, 0, n5-1)<<endl;? ????int arr6[] = {5, 6, 7, 1, 2, 3, 4};? ????int n6 = sizeof(arr6)/sizeof(arr6[0]);? ????cout<<"The minimum element is "<<findMin(arr6, 0, n6-1)<<endl;? ????int arr7[] = {1, 2, 3, 4, 5, 6, 7};? ????int n7 = sizeof(arr7)/sizeof(arr7[0]);? ????cout << "The minimum element is " << findMin(arr7, 0, n7-1) << endl;? ????int arr8[] = {2, 3, 4, 5, 6, 7, 8, 1};? ????int n8 = sizeof(arr8)/sizeof(arr8[0]);? ????cout << "The minimum element is " << findMin(arr8, 0, n8-1) << endl;? ????int arr9[] = {3, 4, 5, 1, 2};? ????int n9 = sizeof(arr9)/sizeof(arr9[0]);? ????cout << "The minimum element is " << findMin(arr9, 0, n9-1) << endl;? ????return 0;? }? // This is code is contributed by rathbhupendra ```