链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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
思路分析
- 本题属于对（有序）数组进行查找操作，时间复杂度要求在O(log n)，很容易想到二分查找算法（对于二分查找算法，可以参考）
- 本题属于对于传统的有序数组的变形，将有序的数组进行了旋转
- 可以先找出序列旋转的点，即将原有数组划分为两个有序数组，又因为有着时间复杂度的要求，只能用二分查找的方法查找旋转点
- 已知旋转点，就能将其划分为两个有序序列，且这两个序列存在严格的大小关系（一个序列中的任意元素都大于或小于另一个序列中的元素），确定序列之后就可以进行传统的二分查找算法
附代码
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/
数组可以分为两类
- 第一类 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不包含旋转）且nums[0] <= target <= nums[mid]时 high 向前规约；nums[mid] < nums[0]（0 - mid包含旋转），target <= nums[mid] < nums[0]时向前规约（target 在旋转位置到 mid 之间）nums[mid] < nums[0]，nums[mid] < nums[0] <= target时向前规约（target 在 0 到旋转位置之间）- 其他情况向后规约
也就是说
nums[mid] < nums[0]，nums[0] > target，target > nums[mid]三项均为真或者只有一项为真时向后规约。
if nums[0] <= nums[i]那么nums[0]到nums[i]为有序数组,那么当nums[0] <= target <= nums[i]时我们应该在0-i范围内查找；if nums[i] < nums[0]那么在0-i区间的某个点处发生了下降（旋转），那么i+1到最后一个数字的区间为有序数组，并且所有的数字都是小于nums[0]且大于nums[i]，当target不属于nums[0]到nums[i]时（target <= nums[i] < nums[0] or nums[i] < nums[0] <= target），我们应该在0-i区间内查找。
上述三种情况可以总结如下：nums[0] <= target <= nums[i] target <= nums[i] < nums[0] nums[i] < nums[0] <= target所以我们进行三项判断：
(nums[0] <= target)， (target <= nums[i]) ，(nums[i] < nums[0])，现在我们想知道这三项中有哪两项为真（明显这三项不可能均为真或均为假（因为这三项可能已经包含了所有情况））
所以我们现在只需要区别出这三项中有两项为真还是只有一项为真。
使用 “异或” 操作可以轻松的得到上述结果（两项为真时异或结果为假，一项为真时异或结果为真，可以画真值表进行验证）
之后我们通过二分查找不断做小 target 可能位于的区间直到 low==high，此时如果 nums[low]==target 则找到了，如果不等则说明该数组里没有此项。
附代码
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;
}
};
相关题目
- 搜索旋转排序数组 II（）
