二分查找：红蓝染色法

BinarySearch

• 一般的二分查找是找到目标值后直接返回结果，若是继续二分查找下去，最终 left == right 时，left 左边的数一定是小于 target 的。

• 代码

public class L34 {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(searchRange(nums, 8)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int start = sel(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = sel(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    /**
     * 寻址目标值第一次出现的位置，通过二分查找，若能找到，第一个必定是 left
     *
     * @param nums nums
     * @param target target
     * @return res
     */
    private static int sel(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

public class L162 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(findPeakElement(nums));
    }

    /**
     * 二分法寻找峰值，设峰值及其右侧为蓝色，左侧为红色，最右侧为蓝色
     * <p>
     *    类似于求函数的极大值
     * </p>
     *
     * @param nums nums
     * @return res
     */
    public static int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 2;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

public class L153 {

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println(findMin(nums));
    }

    /**
     * 二分法寻找最小值，mid 值只需和端点值比较即可。
     *
     * @param nums nums
     * @return res
     */
    public static int findMin(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[len - 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left];
    }
}

public class L33 {

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(search(nums, 0));
    }

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 2;
        int mid;
        while(left <= right) {
            mid = left + (right - left) / 2;
            if(isBlue(nums, target, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left < nums.length && nums[left] == target ? left : -1;
    }

    public static boolean isBlue(int[] nums, int target, int mid) {
        int end = nums[nums.length - 1];
        if(nums[mid] > end) {
            return target > end && nums[mid] >= target;
        } else {
            return target > end || nums[mid] >= target;
        }
    }
}