关于二分查找算法的一些细节

1、二分查找的基本介绍

二分查找，是一个非常高效的算法，主要用于从有序（默认递增）的区间中寻找某个符合条件的值。算法的思想也很简单：

确定搜索区间端点和
计算区间中点，如果是奇数我们通常下取整，即
将中点的值与目标值进行比较，如果：
- 相等，返回中点位置
- 中点的值大于目标值，将区间缩小到至左半部分，即缩小
- 中点的值小于目标值，将区间缩小到至右半部分，即增大
重复以上步骤，直到：
- 找到目标值
- 搜索区间为空

在代码实现上需要注意的细节

算法原理非常简单不过多赘述。下面主要是讲一些具体的实现细节，否则有的时候不注意就把算法写成死循环，或者数组越界。

1、写开区间还是闭区间？什么时候退出循环？

在实现二分查找的时候，相比于算法，区间的定义实际上是最重要的问题。这个问题直接影响到了初始的定义，的更新以及循环的退出条件，十分重要。因此，有必要明确一下什么是“区间”：

可以做如下定义：区间指的是每一次二分查找过程中的搜索区间，区间由左右端点组成，不妨用left和right表示，在搜索过程中，时刻保持着：区间内的值还没有被确定，而区间外的值已经被确定。这句话隐含的信息是：目标值一定在区间内，而不在区间外。

但是，区间的边界问题是代码实现比较头疼的问题。与数学上的区间表示类似，区间可以是开区间，也可以是闭区间。因此，搜索区间可以分为四种情况：

左闭右闭区间[left,right]，表示：left和right都可能是目标值。
左闭右开区间[left,right)，表示：left可能是目标值，但right一定不是目标值（因为right在区间外）。
左开右闭区间(left,right]，表示：right可能是目标值，但left一定不是目标值。
左开右开区间(left,right)，表示：left和right都不可能是目标值。

对于这四种情况，平时常用的主要是三种：[left,right]、[left,right)、(left,right]，左闭右开和左开右闭只是左右调换了一下，没有明显区别，因此下面主要介绍这两种区间的写法。

左闭右闭区间

初始赋值：

假设n为数组长度，初始条件设置时，left左端点为0，右端点为n-1，这样才符合“left和right都可能是目标值”这个定义，且初始时搜索区间覆盖了整个数组。

区间端点的更新：

假设某次查找mid>target，此时要更新right，那么应该是right=mid还是right=mid-1呢？根据定义，“left和right都可能是目标值”，而mid已经被确定不是目标值，因此一定要将其排除在外，那么答案就很明显了，right要更新为right=mid-1。对于left更新也是同理，要更新为left=mid+1。

退出循环条件：

首先明确：当区间刚好为空时才可以退出循环，我们考虑left==right的情况，此时区间为[left,right]，由于两边都是闭区间，所以区间不为空，还要再查找一次，因此条件为left<=right。这样，细节问题就解决了，左闭右闭区间的常见写法如下：

let (mut l, mut r) = (0, n - 1);
while l <= r { 
    let mid = (l + r) / 2;
    if arr[mid] < target {
        l = mid + 1;
    } else {
      	// >=target都会走这个分支，如果需要的话，可以把==这个条件单独提出来
        r = mid - 1;
    }
}

循环结束时：right在left的左边，即right+1=left

左闭右开区间

为了以示区别，用红色来表示与左闭右闭区间的不同点。

初始赋值：

假设n为数组长度，初始条件设置时，left左端点为0，右端点为n，这样即可符合“left可能是目标值，但right一定不是目标值”这个定义，且初始时搜索区间覆盖了整个数组。

区间端点的更新：

假设某次查找mid>target，此时要更新right，那么应该是right=mid还是right=mid-1呢？根据定义，“left可能是目标值，但right一定不是目标值”，而mid已经被确定不是目标值，因此一定要将其排除在外，在这种情况下，right只需要更新为right=mid，那么新的区间就是[left,mid)，符合定义。由于left是闭区间，与左闭右闭区间一样，要更新为left=mid+1。

退出循环条件：

首先明确：当区间刚好为空时才可以退出循环，我们考虑left==right的情况，此时区间为[left,right)，区间已经为空，因此条件为left<right。左闭右开区间的常见写法如下：

let (mut l, mut r) = (0, n);
while l < r { 
    let mid = (l + r) / 2;
    if arr[mid] < target {
        l = mid + 1;
    } else {
      	// >=target都会走这个分支，如果需要的话，可以把==这个条件单独提出来
        r = mid;
    }
}

循环结束时：left和right在同一个位置。

2、防止溢出小细节

对于java、rust、c等语言，有时候可能会遇到在32位整型计算溢出的情况，不想去类型转换的话，可以这样处理：

1	let mid = left + (right - left) / 2

3、如何查找>，>=，<，<=？

下面这一段参考了：0X3F的讲解

二分搜索要处理的问题有一部分都是这样描述的：寻找第一个??x的值。这里的??可以替换为大于/大于等于/小于/小于等于。这就比较头疼，有没有一种方法可以一次处理这四种情况呢？首先这种方法必须是整数数组，假设问题是这样：给定一个整数数组arr是单调非递减排列的，长度为n，给定一个目标target，要求返回数组中第一个??target的位置，如果不存在则返回-1。

首先来看>=的情况。

大于等于

返回数组中第一个>=target的位置。以上面左闭右闭的写法为例：

let (mut l, mut r) = (0, n - 1);
while l <= r { 
    let mid = (l + r) / 2;
    if arr[mid] < target {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}