【題目鏈接】
33. 搜索旋轉排序數組
【題目描述】
【題解】
對于一個有序數組，我們可以使用二分查找算法來查找某個元素，具體的算法模板可以參考【算法基礎課-算法模板1】基礎算法中二分查找一節的內容。
然而，在這道題目中，數組并不是完全有序的，而是經過旋轉后，只保證了數組的某一部分是有序的。那么，是否仍然可以使用二分查找算法呢？答案是可以的。我們可以利用旋轉數組的性質，通過判斷數組的哪一部分是有序的，來調整查找范圍，從而有效地應用二分查找算法。
通過觀察常規的二分查找算法，我們可以看到 mid 將原本有序的序列劃分為 [l, mid] 和 [mid+1, r] 兩個部分。因此，我們可以借鑒這一思想來解決本題。在這道題中，我們可以通過判斷 [l, mid] 和 [mid+1, r] 這兩部分中哪一部分是有序的，然后根據這個有序部分來調整二分查找的上下邊界。具體而言，若某一部分是有序的，我們就可以判斷目標值 target 是否位于該有序部分內，從而決定是將查找范圍縮小到該部分，還是縮小到另一部分。這種方法使得我們能夠在旋轉數組中有效地找到目標值。
- 如果
[l, mid]是有序數組，且target的大小滿足[nums[l], nums[mid])，則我們應該將搜索范圍縮小至[l, mid - 1]，否則將搜索范圍縮小至[mid + 1, r]。 - 如果
[mid, r]是有序數組，且target的大小滿足(nums[mid], nums[r]]，則我們應該將搜索范圍縮小至[mid + 1, r]，否則將搜索范圍縮小至[l, mid - 1]。
例如：
nums=[4,5,6,7,0,1,2]，其中l=0,r=6,mid=3，[l,mid]是有序數組，
如果target=5，在[l,mid-1]中尋找；
如果target=2，在[mid+1,r]中尋找。
nums=[6,7,0,1,2,3,4,5]，其中l=0,r=6,mid=3，[mid,r]是有序數組，
如果target=6，在[l,mid-1]中尋找；
如果target=4，在[mid+1,r]中尋找。
【AC代碼】
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r) {int mid = l + r >> 1;// 如果找到了目標值，直接返回下標if(nums[mid] == target)return mid;// 判斷哪一部分是有序的if(nums[l] <= nums[mid]) { // 左半部分有序if(nums[l] <= target && target < nums[mid]) r = mid - 1; // 目標在左半部分，縮小右邊界else //l = mid + 1; // 目標不在左半部分，縮小左邊界} else { // 右半部分有序if(nums[mid] < target && target <= nums[r])l = mid + 1; // 目標在右半部分，縮小左邊界elser = mid - 1; // 目標不在右半部分，縮小右邊界} }return -1;}
};
