【LeetCode热题100】--33.搜索旋转排序数组

33.搜索旋转排序数组

对于有序数组，使用二分查找：

该题只保证了部分有序，也能进行二分查找

在常规二分查找时查看当前mid分割出来的两部分[l,mid]和[mid+1,r]，哪个部分是有序的，根据有序的那个部分确定我们该如何改变二分查找的上下界，可以根据有序的部分判断出target在不在这个部分

• 如果[l,mid - 1]是有序数组，且target的大小满足(nums[l],nums[mid])，将搜索范围缩小至[l,mid - 1]，否则在[mid+1,r]中查找
• 如果[mid,r]是有序数组，且target的大小满足(nums[mid+1],nums[r])，则我们应该将搜索范围缩小至[mid+1,r]，否则在[l,mid-1]中查找

对于部分有序需要判断nums[0]与nums[mid]的大小关系

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n==0){
            return -1;
        }
        if(n==1){
            return nums[0] == target ? 0 : -1;
        }
        int l = 0,r = n-1;
        while(l<=r){
            int mid = (l + r) / 2;
            if(nums[mid] == target){
                return mid;
            }
            //说明[l,mid - 1]是有序数组
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target < nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{  //[mid,r]是有序数组
                if(nums[mid] < target && target <= nums[n -1]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return -1;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34