题目描述
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
有一个被旋转过的升序数组，例如原来是[0,1,2,4,5,6,7]，从某个位置为轴旋转为[4,5,6,7,0,1,2]，数组元素不重复，要求以log n的复杂度找到目标数字target。
思路分析
log n的复杂度，升序数组，可以联想到二分查找法，但是这里的数组是旋转过的，所以要考虑基于二分查找的思想进行变种。可以用到数学的中方法——分情况讨论。
基于二分查找，mid = (start + end) / 2;，mid的情况可以分为三种：
-
nums[mid] > nums[start]，这种情况说明顺序断层的点发生在右边，因此左半边是升序的，这时候再判断target的值
- 如果target在nums[start]和nums[mid]之间，因为左半边是升序的，说明target就在左半边的数组中，在[start, mid]中递归查找
-
如果target < nums[start]或target > nums[mid]，说明target在断层的地方或target在左半没有断层继续递增的位置，都说明在右侧，在[mid + 1, end]中递归查找
断层发生在右边
-
nums[mid] > nums[start]，说明在左侧已经发生了断层，因此右侧是顺序的
- 如果target在nums[mid]和nums[end]之间，因为右半边是升序的，说明target就在右半边的数组中，在[mid + 1, end]中递归查找
- 同上，相应的，在[start, mid]中递归查找
-
nums[mid] > nums[start]，说明左边已经查完，在右边[mid + 1, end]中递归查找
断层发生在左边
代码实现
class Solution {
public int search(int[] nums, int target) {
return find(nums, 0, nums.length - 1, target);
}
private int find(int[] nums, int start, int end, int target) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[start] == target) {
return start;
}
if (nums[start] < nums[mid]) {
if (target < nums[start] || target > nums[mid]) {
return find(nums, mid + 1, end, target);
} else {
return find(nums, start, mid - 1, target);
}
} else if (nums[start] > nums[mid]) {
if (target > nums[start] || target < nums[mid]) {
return find(nums, start, mid - 1, target);
} else {
return find(nums, mid + 1, end, target);
}
} else {
return find(nums, mid + 1, end, target);
}
}
}
