LeetCode : 33. Search in Rotated Sorted Array 旋转数组的二分搜索

淡淡的烟草味﹌ 2021-06-24 16:10 401阅读 0赞

**试题**  
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  
**代码**  
这一题与二分搜索的差别在于，存在一个区域纠正措施。  
对于mid位置我们首先判断他是在左边递增序列中还是在右边递增序列中。  
然后根据数组的首尾值进行一个区间的纠正。

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