数组排序二分查找

难度中等

题目描述

解题思路

本题是需要使用二分查找，怎么分是关键，举个例子：

第一类
1011110111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类
22 33 44 55 66 77 11 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
这种情况下，前半部分有序。因此如果 nums[start] <=target第三类
66 77 11 22 33 44 55 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。

作者：reedfan
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

public boolean search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int start = 0;
    int end = nums.length - 1;
    int mid;
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[start] == nums[mid]) {
            start++;
            continue;
        }
        //前半部分有序
        if (nums[start] < nums[mid]) {
            //target在前半部分
            if (nums[mid] > target && nums[start] <= target) {
                end = mid - 1;
            } else {  //否则，去后半部分找
                start = mid + 1;
            }
        } else {
            //后半部分有序
            //target在后半部分
            if (nums[mid] < target && nums[end] >= target) {
                start = mid + 1;
            } else {  //否则，去后半部分找
                end = mid - 1;
            }
        }
    }
    //一直没找到，返回false
    return false;
}