社区首页 >专栏 >LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

原创

大学里的混子

修改于 2019-03-07 08:49:50

67800

代码可运行

文章被收录于专栏：LeetCodeLeetCode

运行总次数：0

代码可运行

33.Search in Rotated Sorted Array

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

题目大意：对于一个旋转后的有序数组经查找操作，注意算法的时间复杂度要求是O(logn)。

思路：对于O(logn)复杂度和有序数组，我们很容易想到采用二分搜索法，但是这个有序的数组经过旋转了，那么我们是否有方法让这个旋转后的数组变为严格意义上的有序数组呢？可以，但是想来想去，这种操作的复杂度会高于O(logn)。因此这种方法行不通。但是我们发现，数组是有两段的，这两段中必定有一段是严格意义上递增的数组，因此，我们就可以这这一段有序的数组上进行二分查找法。

 Share my intuitive thinking: the main idea is that we need to find some parts of array
 that we could adopt binary search on that, which means we need to find some completed 
 sorted parts, then determine whether target is in left part or right part. There is at 
 least one segment (left part or right part) is monotonically increasing.

解法：

    public int search(int[] nums, int target) {
        if (nums == null || nums.length ==0) return -1;
        int left = 0 ,right = nums.length-1,mid;
        while (left<=right){
            mid = left+(right-left)/2;
            if (nums[mid] == target ) return mid;
            if (nums[left] <= nums[mid]){
                //left to mid is monotonically increasing
                if (target < nums[mid] && target>=nums[left]){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else {
                //mid to right is monotonically increasing
                if (target<=nums[right]&& target>nums[mid]){
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
        }
        return  -1;
    }

81.Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

题目大意：对于一个旋转后的有序数组经查找操作，注意这里的数组是有重复数字的。

思路：对于没有重复数字的旋转数组，我们很好的解决了将其转化为严格有序数组的问题，但是这个有重复数字的旋转的数组与上一题有什么区别呢？我们发现，当同样采用上面的思路的时候会存在一种情况：无法根据(nums[left]<= nums[mid])这一句来判断那一段严格的递增了，因为会存在首位是同一个数字的情况，例如： [2,5,6,0,0,1,2]；所以，我们要对这种特殊的情况进行处理，也就是让此时的left和right所指向的数字是不同的，因此我们加入以下的处理：

while(left < right && nums[left]== nums[right]) left++;

这样可以很好的解决上的问题。

解法：

public boolean search (int[] nums, int target) {
        if (nums == null || nums.length ==0) return false;
        int left = 0 ,right = nums.length-1,mid;
        while (left<=right) {
            while (left < right && nums[left] == nums[right]) left++;
            mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            if (nums[left]<=nums[mid]){
                if (target>=nums[left]&&target<nums[mid]){
                    right = mid-1;
                }else left = mid+1;
            }else {
                if (target>nums[mid]&&target<=nums[right]){
                    left = mid+1;
                }else right = mid-1;
            }
        }
        return false;
    }