33. 搜索旋转排序数组
Difficulty: 中等
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [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
思路
这题有两种解法,无论哪种都困住我很长时间去想。。可能还是自己刷得太少也没有相关的经验。
今天先讲第一种思路:
分情况讨论
如果nums[mid] == target ,那么就直接返回mid就可以
如果nums[mid] >= nums[left],那么此时mid在左端数组,且从mid开始,一直到left为止,都是排好序的。可以分为两种情况 (1). nums[mid] > target && target >= nums[left] : 此时的target 在左侧有序数组中,且下标位置小于mid,将right 更新为 mid-1。用二分查找继续处理即可。 (2). 不满足 (1)的条件时,mid 所处下标位置会在mid的右边,所以继续对mid 的右边数组执行 2的操作。将left更新为mid + 1
如果nums[mid] < nums[left], 那么此时mid在右端数组,则mid到right的数组是排好序的。分情况讨论 (1). 如果nums[mid] < target && target < nums[left] ,那么left 所处下标大于mid,将left 更新为 mid+1,然后用二分查找继续处理即可。 (2). 如果不满足(1)的条件,target所处下标位置在mid左边 ,对mid左边的数组继续执行 3 操作。将right 更新为 mid - 1。
Solution
Language: Java
class Solution {
/**
* 复杂解法
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
//二分法
int left = 0;
int right = nums.length - 1;
int mid = 0;
if(nums.length == 0)
{
return -1;
}
while(left <= right)
{
mid = (left + right)/2;
if(nums[mid] == target)
{
return mid;
}
if(nums[mid] > nums[left] )
{
if(nums[mid] > target)
{
if(target > nums[left]){
right = mid -1;
}else if(target < nums[left])
{
left = mid + 1;
}else {
return left;
}
}else {
left = mid + 1;
}
}else if(nums[mid] < nums[left] ) {
if(target > nums[mid] && target < nums[left] )
{
left = mid + 1;
}else{
right = mid - 1;
}
}else{
if(nums[left] == target)
{
return left;
}
if(nums[right] == target)
{
return right;
}
return -1;
}
}
return left;
}
}