把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。
例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為 1。
示例 1：
輸入：[3,4,5,1,2]
輸出：1
示例 2：
輸入：[2,2,2,0,1]
輸出：0
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
思路這是一道二分查找的變種題，數組被分成了兩個部分，每個部分都是有序的，要求查找數組的最小值，時間複雜度
當然
二分查找Ⅰ. 基本模板int binary_search(vector<int> &vec, int target) {
int low = 0, high = vec.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (vec[mid] > target) {
high = mid - 1;
} else if (vec[mid] < target) {
low = mid + 1;
} else {
return mid；
}
}
return -1;
}
或者
int binary_search(vector<int> &vec, int target) {
int low = 0, high = vec.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (vec[mid] > target) {
high = mid;
} else if (vec[mid] < target) {
low = mid + 1;
} else {
return mid；
}
}
return -1;
}
Ⅱ. 題目分析這道題還是有意思的，題目並沒有說數組中不包含重複元素，那就是可能存在重複元素，加上這個題目就不那麼簡單了。
我們定義
任何一個旋轉數組，肯定會被
我們怎麼判斷這這個旋轉數組哪個部分有序呢？通過比較
還剩下幾個問題：
如果 說明右邊有序，所以我們可以判斷最小值肯定在
如果 說明左邊有序，但是因為題目給的旋轉數組的定義( 把一個數組最開始的若干個元素搬到數組的末尾 )，我們可以肯定最小元素在數組右邊
如果我們用
比如：
當 時，我們通過縮小判斷範圍來解決，即
參考 面試題 11. 旋轉數組的最小數字（二分法，清晰圖解）[1]
class Solution {
public:
int minArray(vector<int>& numbers) {
int size = numbers.size();
int left = 0, right = size - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (numbers[mid] < numbers[right]) {
right = mid;
} else if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else {
--right;
}
}
return numbers[left];
}
};
// 這樣寫也是可以的~
// class Solution {
// public:
// int findMin(vector<int>& nums) {
// int size = nums.size();
// int left = 0, right = size - 1;
// int ans = INT_MAX;
// while (left <= right) {
// int mid = left + (right -left) / 2;
// if (nums[mid] < nums[right]) {
// ans = min(ans, nums[mid]);
// right = mid - 1;
// } else if (nums[mid] > nums[right]) {
// left = mid + 1;
// } else {
// --right;
// }
// }
// return min(ans, nums[left]);
// }
// };
class Solution:
def minArray(self, numbers: List[int]) -> int:
left, right = 0, len(numbers) - 1
while left < right:
mid = (left + right) // 2
if numbers[mid] < numbers[right]:
right = mid
elif numbers[mid] > numbers[right]:
left = mid + 1
else:
right -= 1
return numbers[left]
總結這個題還是比較難的，值得思考，初次遇到估計很難想到，細節太多了。
相似的題33. 搜索旋轉排序數組[2]
153. 尋找旋轉排序數組中的最小值[3]
如果理解了怎麼壓縮邊界，縮小範圍，這兩道題肯定就是很簡單的了。這兩道題都是數組中不包含重複元素的！！！
class Solution {
public:
int search(vector<int>& nums, int target) {
int size = nums.size();
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > nums[right]) {
// 說明左邊有序，看看要查找的target在不在左邊，因為是有序的，所以只要滿足 nums[left] <= target < nums[mid]
// 就能確定target在左邊了，否則，就不在左邊，要去右邊找。
if (nums[mid] > target && target >= nums[left]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 說明右邊有序，同左邊有序，判斷target在不在右邊，在右邊就在右邊找，不在就在左邊找。
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};
class Solution {
public:
int findMin(vector<int>& nums) {
int size = nums.size();
int left = 0, right = size - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
};
參考[1]面試題 11. 旋轉數組的最小數字（二分法，清晰圖解）: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
[2]33. 搜索旋轉排序數組: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[3]153. 尋找旋轉排序數組中的最小值: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
- END -