鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
題目描述
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
思路分析
- 本題屬于對（有序）數(shù)組進(jìn)行查找操作，時(shí)間復(fù)雜度要求在O(log n)，很容易想到二分查找算法（對于二分查找算法，可以參考）
- 本題屬于對于傳統(tǒng)的有序數(shù)組的變形，將有序的數(shù)組進(jìn)行了旋轉(zhuǎn)
- 可以先找出序列旋轉(zhuǎn)的點(diǎn)，即將原有數(shù)組劃分為兩個(gè)有序數(shù)組，又因?yàn)橛兄鴷r(shí)間復(fù)雜度的要求，只能用二分查找的方法查找旋轉(zhuǎn)點(diǎn)
- 已知旋轉(zhuǎn)點(diǎn)，就能將其劃分為兩個(gè)有序序列，且這兩個(gè)序列存在嚴(yán)格的大小關(guān)系（一個(gè)序列中的任意元素都大于或小于另一個(gè)序列中的元素），確定序列之后就可以進(jìn)行傳統(tǒng)的二分查找算法
附代碼
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if(len == 0) return -1;
if(len == 1) {
if(target == nums[0]) {
return 0;
}
else {
return -1;
}
}
if(nums[0] < nums[len-1]) {
int beg = 0;
int end = len - 1;
int mid = (beg + end) / 2;
while(beg <= end) {
if(nums[mid] == target) return mid;
else if(nums[mid] < target) {
beg = mid + 1;
}
else {
end = mid - 1;
}
mid = (beg + end) / 2;
}
return -1;
}
int beg = 0;
int end = len - 1;
int tmp = (beg + end) / 2;
while(beg <= end) {
if(tmp == 0 && nums[tmp] > nums[tmp+1] || tmp == len - 1 && nums[tmp] < nums[tmp-1])
break;
if(tmp != 0 && tmp != len - 1 && nums[tmp] > nums[tmp-1] && nums[tmp] > nums[tmp+1]) {
break;
}
if(nums[tmp] > nums[len - 1]) {
beg = tmp + 1;
tmp = (beg + end) / 2;
}
else {
end = tmp - 1;
tmp = (beg + end) / 2;
}
}
if(target >= nums[0]) {
end = tmp;
beg = 0;
int mid = (beg + end) / 2;
while(beg <= end) {
if(nums[mid] == target) return mid;
else if(nums[mid] < target) {
beg = mid + 1;
}
else {
end = mid - 1;
}
mid = (beg + end) / 2;
}
return -1;
}
else if(target <= nums[len - 1]) {
beg = tmp + 1;
end = len - 1;
int mid = (beg + end) / 2;
while(beg <= end) {
if(nums[mid] == target) return mid;
else if(nums[mid] < target) {
beg = mid + 1;
}
else {
end = mid - 1;
}
mid = (beg + end) / 2;
}
return -1;
}
else
return -1;
}
}
- 作者：reedfan
鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-bai-liao-9983de-javayong-hu-by-reedfan/
數(shù)組可以分為兩類
- 第一類 2 3 4 5 6 7 1 這種，也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5。
這種情況下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，則在前半部分找，否則去后半部分找。- 第二類 6 7 1 2 3 4 5 這種，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2。
這種情況下，后半部分有序。因此如果 nums[mid] <target<=nums[end]，則在后半部分找，否則去前半部分找。
附代碼
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
//前半部分有序,注意此處用小于等于
if (nums[start] <= nums[mid]) {
//target在前半部分
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
else {
if (target <= nums[end] && target > nums[mid]) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
}
return -1;
}
- 作者：LukeLee
鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
nums[0] <= nums[mid]（0 - mid不包含旋轉(zhuǎn)）且nums[0] <= target <= nums[mid]時(shí) high 向前規(guī)約；nums[mid] < nums[0]（0 - mid包含旋轉(zhuǎn)），target <= nums[mid] < nums[0]時(shí)向前規(guī)約（target 在旋轉(zhuǎn)位置到 mid 之間）nums[mid] < nums[0]，nums[mid] < nums[0] <= target時(shí)向前規(guī)約（target 在 0 到旋轉(zhuǎn)位置之間）- 其他情況向后規(guī)約
也就是說
nums[mid] < nums[0]，nums[0] > target，target > nums[mid]三項(xiàng)均為真或者只有一項(xiàng)為真時(shí)向后規(guī)約。
if nums[0] <= nums[i]那么nums[0]到nums[i]為有序數(shù)組,那么當(dāng)nums[0] <= target <= nums[i]時(shí)我們應(yīng)該在0-i范圍內(nèi)查找；if nums[i] < nums[0]那么在0-i區(qū)間的某個(gè)點(diǎn)處發(fā)生了下降（旋轉(zhuǎn)），那么i+1到最后一個(gè)數(shù)字的區(qū)間為有序數(shù)組，并且所有的數(shù)字都是小于nums[0]且大于nums[i]，當(dāng)target不屬于nums[0]到nums[i]時(shí)（target <= nums[i] < nums[0] or nums[i] < nums[0] <= target），我們應(yīng)該在0-i區(qū)間內(nèi)查找。
上述三種情況可以總結(jié)如下：nums[0] <= target <= nums[i] target <= nums[i] < nums[0] nums[i] < nums[0] <= target所以我們進(jìn)行三項(xiàng)判斷：
(nums[0] <= target)， (target <= nums[i]) ，(nums[i] < nums[0])，現(xiàn)在我們想知道這三項(xiàng)中有哪兩項(xiàng)為真（明顯這三項(xiàng)不可能均為真或均為假（因?yàn)檫@三項(xiàng)可能已經(jīng)包含了所有情況））
所以我們現(xiàn)在只需要區(qū)別出這三項(xiàng)中有兩項(xiàng)為真還是只有一項(xiàng)為真。
使用 “異或” 操作可以輕松的得到上述結(jié)果（兩項(xiàng)為真時(shí)異或結(jié)果為假，一項(xiàng)為真時(shí)異或結(jié)果為真，可以畫真值表進(jìn)行驗(yàn)證）
之后我們通過二分查找不斷做小 target 可能位于的區(qū)間直到 low==high，此時(shí)如果 nums[low]==target 則找到了，如果不等則說明該數(shù)組里沒有此項(xiàng)。
附代碼
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}
};
相關(guān)題目
- 搜索旋轉(zhuǎn)排序數(shù)組 II（）
