二分搜索的变形

总结一下：

1、数组中的数不重复，最简单的情况

1、最普通的二分查找：leetcode704
/**
 * 二分查找：nums 中的所有元素是不重复的
 */
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;  // 左闭右闭
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }   // 终止条件left == right，后面就不用混淆ans究竟用left还是right了
        // nums[left]还未判断
        return nums[left] == target? left: -1;
    }
}

2、二分查找：寻找第一个等于target和最后一个等于target的元素 leetcode34（数组中的元素有重复）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        return new int[]{firstEquals(nums, target), lastEquals(nums, target)};
    }

    // 寻找第一个等于target的元素
    public int firstEquals(int[] nums, int target) {
        int left = 0, right = nums.length - 1;  // 左闭右闭
        while (left < right) {
            int mid = left + ((right - left) >> 1); // 向下取整
            if (nums[mid] == target) {
                right = mid;    // [target target]
            } else if (nums[mid] > target) {
                right = mid;    // [2 2] target = 1 宁可少缩放一点，也不能越界，不能写成mid-1
            } else {
                left = mid + 1;
            }
        }
        // 特判 nums[left]
        if (nums[left] == target && (left == 0 || nums[left-1] < target)) return left;
        return -1;  // 没找到
    } 

    // 寻找最后一个等于target的元素
    public int lastEquals(int[] nums, int target) {
        int left = 0, right = nums.length - 1;  // 左闭右闭
        while (left < right) {
            int mid = left + ((right - left + 1) >> 1);    // 向上取整
            if (nums[mid] == target) {  // [target target]
                left = mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid; // // [2 2] target = 3 宁可少缩放一点，也不能越界，不能写成mid+1 
            }
        }
        if (nums[left] == target && (left == nums.length - 1 || nums[left+1] > target)) return left;
        return -1;　　// 没找到
    }
}

3、查找第一个大于等于给定值的元素 leetcode35

class Solution {
    public int firstLargeOrEquals(int[] nums, int target) {
        int left = 0, right = nums.length - 1;　　// 左闭右闭
        while (left < right) {
            int mid = left + ((right - left) >> 1);　　// 向下取整
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;    // 查找大于等于给定元素 mid属于解空间
            }
        }
        if (nums[left] >= target && (left == 0 || nums[left-1] < target)) return left;　　// 大于等于给定元素
        return -1；    // 没找到说明都比target小 （有的题目会让 放到最后即可）
    }
}

4、查找最后一个小于等于给定值的元素

private int lastLessOrEquals(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);　　// 向上取整
        if (arr[mid] > target) r = mid - 1;
        else l = mid; // 查找小于等于target的位置，
    }
    if (arr[l] <= target && (l == arr.length - 1 || arr[l + 1] > target)) return l; // <=
    return -1;　　// 没找到说明都比target大 （有的题目会让 放到第一个位置）
}