施工完毕
二分算法是分治中的一种，所谓二分，其实就是将一个较大的问题缩小x区间去求解废话不多说详情请见百度
我个人认为二分有点儿难，主要要将l,r与mid处理好
Knuth(好像是他发明的KMP 来着）曾经说过

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky

思路很简单，细节是魔鬼。

First二分查找

额，k才开始学习二分时，没弄懂二分查找的用途好处，觉得它还是停留在暴力上面。我总结了一下二分查找的关键 ~~福利来了~~

二分查找的框架

int binarySearch(int[] nums, int target/*指定数 ~~上网找到的单词~~*/) {
 int left = 0, right = ...;//注意 也有可能l不是0！

 while(.../*循环次数，一般l == r就结束了*/) {
     int mid = (right + left) / 2;//找到mid
     if (nums[mid] == target) {//满足条件，跳出循环...
         ...
     } else if (nums[mid] < target) {//小于指定数，调整左边界
         left = ...//跟题目判定是mid+1还是mid
     } else if (nums[mid] > target) {//大于指定数，调整右边界
         right = ...//跟题目判定是mid-1还是mid
     }
 }
 return ...;
}

在找数的例题中，代码也和它相差无几

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意 如果觉得麻烦，可以在函数里添加一个系数n来表示数组长度

    while(left <= right) { // 注意，这是一个闭区间搜索！
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就可能出现错误。
假如如果一不留神，代码溢出了怎么办凉拌 请用 mid = left + (right - left) / 2 ！！

搜索左右边界

左边界

int left_bound(int[] nums, int target) {
 if (nums.length == 0) return -1;
 int left = 0;
 int right = nums.length; // 注意

 while (left < right) { // 注意
     int mid = (left + right) / 2;
     if (nums[mid] == target) {
         right = mid;
     } else if (nums[mid] < target) {
         left = mid + 1;
     } else if (nums[mid] > target) {
         right = mid; // 注意找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左 // 收缩，达到锁定左侧边界的目的。
     }
 }
 return left;
}

右边界

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;//当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧 //边界的目的。
        }
    }
    return left - 1; // 注意while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 //好了。

last最终总结

第一个，最基本的二分查找算法：
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
第二个，寻找左侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
第三个，寻找右侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

二分总结

First二分查找

二分查找的框架

搜索左右边界

last最终总结