算法之二分查找

1.二分法的循环条件总结：

左闭右开的形式：循环条件一定是 while(left < right)。由于左闭，所以 left = mid + 1;。由于右开，所以 right = mid;。最后循环结束时，left == right 。

左闭右闭的形式：循环条件一定是 while(left <= right)。由于左闭，所以 left = mid + 1;。由于右闭，所以 right = mid - 1;。最后循环结束时，left == right + 1

2.左闭右开代码实现：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;  // 定义target在左闭右开的区间里，即：[left, right)
        while(left < right){  // 因为left == right的时候，在[left, right)是空区间，所以使用小于号
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;  // target 在右区间，在[mid + 1, right)中
            }else if(nums[mid] > target){  
                right = mid;  // target 在左区间，在[left, mid)中
            }else{  // nums[mid] == target
                return mid;  // 数组中找到目标值，直接返回下标
            }
        }
        return -1;  // 未找到目标值
    }
}

3.左闭右闭代码实现

int lower_bound(int[] nums, int target){
    int left = 0, right = nums.length - 1;
    while(left <= right){  // 定义target在左闭右闭的区间里，即：[left, right]
        int mid = left + (right - left) / 2;
        if(nums[mid] < target){
            left = mid + 1;  // target 在右区间，在[mid + 1, right]中
        }else{
            right = mid - 1;  // target 在左区间，在[left, mid - 1]中
        }
    }
    return left;  // 此时 left == right + 1
}

以上是我个人的学习心得，能力有限，如有错误和建议，恳请批评指正！