前言

之前对二分理解不够透彻，现在学习后又有点心得了。

二分法之我个人最容易理解的写法

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 注意
    while(left <= right) {
        int mid = left + (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;
}

这个写法重点在于，是闭区间，因为对mid位置，如果不满足，缩减就是mid-1和mid+1。但是这样会有一种情况发生，那就是对于[1，2，2，2，3]，我们无法利用找到左侧边界的2以及右侧边界的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; // 注意
        }
    }
    return left;
//也可以判断，如果left越界了，就应该返回-1，表示没有找到
}

左侧边界的写法，首先变化的就是由原来的闭区间变成了开区间，整个区间是[0，nums.length)。因此，while中也变成了小于，而不再是等于。
本例中，如果在相等时，直接返回就和上面的普通写法一样，但是注意，左侧边界的代码中，写法时right=mid，相等时，不断缩小右边的范围，这样就能形成左侧边界的搜索。

左侧边界的不搜索的二分

正如左侧搜索中提到的，不搜索，直接返回自然也是可以的，

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) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;

右侧边界搜索的二分

所有右侧边界的搜索也很容易理解了，相等时，缩小左侧区域，由于左边是闭区间，所以，相等时，是左侧+1，

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;
        }
    }
    return left - 1; // 注意
}

右侧边界不搜索

直接返回

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) {
            return mid; 
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

补充

如果非要用闭区间进行搜索，以右侧为例

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            left = mid + 1;
        }
    }
    // 需要检查越界
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

左侧的也不难

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            right = mid - 1;
        }
    }
    // 需要检查越界
// 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}