转载

[Leetcode] Search in Rotated Sorted Array 搜索旋转有序数组

Search in Rotated Sorted Array I

Suppose a sorted array 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.

二分法

复杂度

时间 O(logN) 空间 O(1)

思路

平时我们二分法的时候，直接判断下中点和目标的关系，就可以知道目标在左半部分还是右半部份了，这背后其实隐含一个假设，那就是从起点到终点是一段有序的序列。而本题中，如果我们还想继续做二分法，这个假设就不存在了，因为从起点到终点有可能有个断片！不过，旋转有序数组有一个特点，假设本身是个升序序列，从左向右。如果左边的点比右边的点小，说明这两个点之间是有序的，不存在旋转点。如果左边的点比右边的大，说明这两个点之间有一个旋转点，导致了不再有序。因为只有一个旋转点，所以一分为二后，肯定有一半是有序的。所以，我们还是可以用二分法，不过要先判断左半边有序还是右半边有序。如果左半边有序，则直接将目标和左半边的边界比较，就知道目标在不在左半边了，如果不在左半边肯定在右半边。同理，如果右半边有序，则直接将目标和右半边的边界比较，就知道目标在不在右半边了，如果不在右半边肯定在左半边。这样就完成了二分。

注意

这里要注意二分时候的边界条件，一般来说我们要找某个确定的目标时，边界条件为：

min = 0, max = length - 1; if(min <= max){     min = mid + 1     max = mid - 1 }

另外，判断左半边是否有序的条件是： nums[min] <= nums[mid] ，而判断是否在某一个有序区间，则要包含那个区间较远的那一头

代码

迭代写法

public class Solution {  public int search(int[] nums, int target) {   int min = 0, max = nums.length - 1, mid = 0;   while(min <= max){    mid = (min + max) / 2;    if(nums[mid] == target){     return mid;    }    // 如果左半部分是有序的    if(nums[min] <= nums[mid]){     if(nums[min] <= target && target < nums[mid]){      max = mid - 1;     } else {      min = mid + 1;     }     // 如果右半部份是有序的    } else {     if(nums[mid] < target && target <= nums[max]){      min = mid + 1;      } else {      max = mid - 1;     }    }   }   // 不满足min <= max条件时，返回-1   return -1;  } }

递归写法

public class Solution {  public int search(int[] nums, int target) {   return helper(nums, 0, nums.length - 1, target);  }  public int helper(int[] nums, int min, int max, int target){   int mid = min + (max - min) / 2;   // 不满足min <= max条件时，返回-1   if(min > max){    return -1;   }   if(nums[mid] == target){    return mid;   }   // 如果左半部分是有序的   if(nums[min] <= nums[mid]){    // 如果在左半部分的边界内    if(nums[min] <= target && target < nums[mid]){     return helper(nums, min, mid - 1, target);    // 如果不在左半部分的边界内    } else {     return helper(nums, mid + 1, max, target);    }   // 如果右半部份是有序的   } else {    // 如果在右半部分的边界内    if(nums[mid] < target && target <= nums[max]){     return helper(nums, mid + 1, max, target);    // 如果不在右半部分的边界内    } else {     return helper(nums, min, mid - 1, target);    }   }  } }

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

二分法

复杂度

时间 O(N) 空间 O(1)

思路

如果可能有重复，那我们之前判断左右部分是否有序的方法就失效了，因为可能有这种 13111 情况，虽然起点小于等于中间，但不代表右边就不是有序的，因为中点也小于等于终点，所有右边也是有序的。所以，如果遇到这种中点和两边相同的情况，我们两边都要搜索。

代码

public class Solution {  public boolean search(int[] nums, int target) {   return helper(nums, 0, nums.length - 1, target);  }  public boolean helper(int[] nums, int min, int max, int target){   int mid = min + (max - min) / 2;   // 不符合min <= max则返回假   if(min > max){    return false;   }   if(nums[mid] == target){    return true;   }   boolean left = false, right = false;   // 如果左边是有序的   if(nums[min] <= nums[mid]){    // 看目标是否在左边有序数列中    if(nums[min] <= target && target < nums[mid]){     left = helper(nums, min, mid - 1, target);    } else {     left = helper(nums, mid + 1, max, target);    }   }   // 如果右边也是有序的   if(nums[mid] <= nums[max]){    // 看目标是否在右边有序数列中    if(nums[mid] < target && target <= nums[max]){     right = helper(nums, mid + 1, max, target);    } else {     right = helper(nums, min, mid - 1, target);    }   }   // 左右两边有一个包含目标就返回真   return left || right;  } }

正文到此结束