Thinking process

分类讨论

如果无法合并就分开讨论

画图辅助

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int start = 0;
        int end = nums.length - 1;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[start] < nums[mid]) {
                if (nums[mid] < target || nums[start] > target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                if (nums[mid] < target && nums[start] > target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }

        if (nums[start] == target) return start;
        if (nums[end] == target) return end;

        return -1;

    }
}

Follow-ups => LC 81

what if duplicates are allowed?

worst case => O(n)

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;

        int start = 0;
        int end = nums.length - 1;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (nums[mid] == target) {
                return true;
            } else if (nums[start] < nums[mid]) {
                if (nums[mid] < target || nums[start] > target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else if (nums[start] > nums[mid]){
                if (nums[mid] < target && nums[start] > target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                start++;
            }
        }

        return nums[start] == target || nums[end] == target;

    }
}