二分查找的模板写法

## 二分查找用于有序或者部分有序的数组查找
## 收缩可能为空集
- 如果二分查找最终可能存在查不到的情况（无论是查找点或者区间），则必须这么写。
- 这是比较万能一点的写法，但缺点是通常需要额外判断left，right的越界情况，以及查找的结果情况。
```
while(left<=right)
{
    mid = (left + right)>>1;
    if(...)
    {
        right = mid -1; 
    }
    else if(...)
    {
        left = mid + 1;
    }
    else ...
}
//这里通常需要额外的判断，可以通过left位置的情况，判断是否查找到了target
if(left>=nums.size() || right < 0 || (nums[left]!=target))
{
    ...
}
//比如这个题：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
```
## 收缩为一个点
- 这是比较常见的情况，也即最终left和right最终必然会收缩成一点,也有可能存在找不到target的情况，也需要判断。但比前面简单的地方在于，[left，right]不会越出[0,nums.size()-1]的范围，判断条件简单一点：
```
while(left < right)
{
    mid = ...;
    if(...)
    {
        right = mid;
    }
    else
    {
        left = mid + 1;
    }
}

//跳出循环后，left==right，left或者right都可以是我们需要的结果，只需简单判断一下
if(nums[left]!=target)
{
    //说明没找到
}

//比如这个题：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
```
- 因为C++默认的除法特性，即(1+2)/2 == 1这样的原因，像这样写可能造成死循环，因此不能这样写，除非不使用“地板除”：
```
while(left < right)
{
    mid = ...;
    if(...)
    {
        right = mid - 1;   
    }
    else
    {
        left = mid;  //最终收缩时，这里可能死循环
        //比如left+1 = right时，mid == left, 此时如果判断条件进入此处，则left不变，right也不变，造成无法跳出left<right的条件
    }
}

```
使用floor函数。floor(x)返回的是小于或等于x的最大整数。如：
```
    floor(2.5) = 2
    floor(-2.5) = -3
```
使用ceil函数。ceil(x)返回的是大于x的最小整数。如：
```
    ceil(2.5) = 3
    ceil(-2.5) = -2
    floor()是向负无穷大舍入，floor(-2.5) = -3；ceil()是向正无穷大舍入，ceil(-2.5) = -2。
```
两者都要引用 `#include <math.h>`库

## 收缩为一个区间
这种情况相对比较少，写起来比较简单，用于寻找的是一个区间的情况，left和right最终会收缩成一个只有两个元素的区间（如果这样的区间可能不存在，则while外面需要额外判断）：
```
while(left < right - 1)
{
     if(...)
    {
        right = mid;
    }
    else
    {
        left = mid;
    }
}

//额外判断，left，right不会越出[0,nums.size()-1]
    if(...)
    {
    
    }
```
如果是寻找一个区间，但是这样的区间又可能不存在，则也可使用第一种写法并做判断。

## 总结
三种写法差不太多，主要是while循环结束时的判断条件不一样，一般使用第二种即可。

lee-romantic 's Blog

导航

最近发表

友情链接