33.搜索旋轉(zhuǎn)排序數(shù)組
整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。
在傳遞給函數(shù)之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數(shù)）。例如， [0,1,2,4,5,6,7] 在下標 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標值 target ，則返回它的下標，否則返回 -1 。
你必須設計一個時間復雜度為 O(log n) 的算法解決此問題。
示例 1：
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4
示例 2：
輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1
示例 3：
輸入：nums = [1], target = 0
輸出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104-
nums中的每個值都 獨一無二 - 題目數(shù)據(jù)保證
nums在預先未知的某個下標上進行了旋轉(zhuǎn) -104 <= target <= 104
官方題解思路：這道題中，數(shù)組本身不是有序的，進行旋轉(zhuǎn)后只保證了數(shù)組的局部是有序的，這還能進行二分查找嗎？答案是可以的
將數(shù)組從中間分開成左右兩部分的時候，一定有一部分的數(shù)組是有序的。
拿示例來看，[0,1,2,4,5,6,7]分開以后數(shù)組變成了 [4, 5, 6，7] 和 [0, 1, 2] 兩個部分，其中左邊 [4, 5, 6,7] 這個部分的數(shù)組是有序的，其他也是如此。
我們可以在常規(guī)二分查找的時候查看當前 mid 為分割位置分割出來的兩個部分 [l, mid] 和 [mid + 1, r] 哪個部分是有序的，并根據(jù)有序的那個部分確定我們該如何改變二分查找的上下界，因為我們能夠根據(jù)有序的那部分判斷出 target 在不在這個部分文章來源：http://www.zghlxwxcb.cn/news/detail-789611.html
- 如果 [l, mid - 1] 是有序數(shù)組，且 target 的大小滿足 [nums[l],nums[mid])，則我們應該將搜索范圍縮小至 [l, mid - 1]，否則在 [mid + 1, r] 中尋找。
- 如果 [mid, r] 是有序數(shù)組，且 target 的大小滿足 (nums[mid+1],nums[r]]，則我們應該將搜索范圍縮小至 [mid + 1, r]，否則在 [l, mid - 1] 中尋找。
文章來源地址http://www.zghlxwxcb.cn/news/detail-789611.html
public class Problem_0033_SearchInRotatedSortedArray {
public int search(int[] nums, int target) {
// 題目提示中已經(jīng)表示1 <= nums.length，不需要判空
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (nums[mid] == target) {
return mid;
}
// 前半段有序
if (nums[mid] > nums[end]) {
if (nums[start] <= target && nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
到了這里，關于33.搜索旋轉(zhuǎn)排序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
