31 Search in Rotated Sorted Array ll
描述不包含相同的元素情况
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
对有序数组进行一定的旋转,进行查找
二分查找and双指针
这是二分查找的变体,
双指针的形式,low = 0, high = length-1;
mid 中间分为两个部分
形式
- nums[mid]< nums[r], 这是有序的,可以在这部分进行二分查找
- 如果nums[mid]<target<= nums[r] , 则可以抛弃左边部分
- 否则抛弃右部分
- nums[mid]>nums[r], 则nums[l] 到 nums[mid] 是有序,
- 如果nums[l]<target<=nums[mid], 则在这左部分进行二分查找
- 否则抛弃左部分
找出其中满足二分查找的部分
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length==0) return -1;
int n = nums.length;
int l=0,right = n-1;
while(right>=l)
{
int mid = (l+right)/2;
if(nums[mid]==target)
return mid;
//在这里也可以换成nums[left], 比较
if(nums[mid] < nums[right])
{
if(nums[mid]<target && nums[r]>=target)
{
l = mid+1;
}
else
right = mid-1;
}
else
{
if(nums[l]<= target && nums[mid]>target )
right = mid-1;
else
l = mid+1;
}
}
return -1;
}
}
另一种方式写法情况, 主要跟nums[left]与nums[mid]
public class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) return true;
if (nums[mid] == nums[left]) left++;
else if (nums[mid] > nums[left]) {
if (nums[left] <= target && nums[mid] > target) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}
}
复杂度
二分查找时间复杂度为olog(N), 空间复杂度为O(1)
81题目
-
如果包含相同元素,那么就有可能在两边都有都有相同的元素,
-
你并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步,直到边缘和中间不在相等或者相遇,这就导致了会有不能切去一半的可能。
-
所以最坏情况(比如全部都是一个元素,或者只有一个元素不同于其他元素,而他就在最后一个)就会出现每次移动一步,总共是n步,算法的时间复杂度变成O(n)。代码如下:
所以比较 nums[mid] 与nums[right], 如果两个相等,则放弃一遍的,放弃右边的
if(nums[mid]==nums[right])
right--;
所以就增加了一种情况,
在31题目中
- nums[mid]>nums[right]
- nums[mid] < nums[right]
在81题中
- nums[mid]<nums[right]
- nums[mid]>nums[right]
- nums[mid] =nums[right]
class Solution {
public boolean search(int[] nums, int target) {
if(nums==null||nums.length==0) {return false;}
int n = nums.length;
int l=0,r = n-1;
while(r>=l)
{
int mid = (l+r)/2;
if(nums[mid]==target)
return true;
if(nums[mid] < nums[r])
{
if(nums[mid]<target && nums[r]>=target)
{
l = mid+1;
}
else
{ r = mid-1;}
}
else if(nums[mid]>nums[r])
{
if(nums[l]<= target && nums[mid]>target )
{
r = mid-1;
}
else
{
l = mid+1;
}
}
else {
--r;
}
}
return false;
}
}