六款二分查找模板，哪款才是你的菜？

随心源

14585

2022.05.21

2022.07.09

发布于未知归属地

二分查找技术交流

§ 前言
§ 算法简介
§ 模板介绍
§ 模板总结
§ 模板投票

§ 前言

2020年5月20日，每日一题，一道典型的二分查找题，很多同学应该都被第18个测试用例调戏了一把，衷心祝愿我们可爱的力扣小编一辈子单身，也真诚祝愿广大扣友没有对象的早日脱单，有对象的幸福美满。

很多同学觉得二分查找无比困难，如双指针移动，边界条件判断等等，是不是困扰你很久了？
这不？如果你还没有在众多二分查找模板中找到一位女友，六位沉鱼落雁，闭月羞花的美女正向您走来，环肥燕瘦，各有千秋！总有一款适合您！

§ 算法简介

二分查找也称折半查找，它是一种效率较高的查找方法。
对一个长度为 $n$ 的有序数组，线性查找时间复杂度为 $O (n)$ ，二分查找时间复杂度为 $O (lo g n)$ 。

对此，世界服和国服都有详细讲解。
LeetCode Explore Binary Search
LeetBook 二分查找

截止至2022年5月20日，力扣共计2642题，算法二分查找标签收录204题，排在动态规划，搜索（深度优先搜索、广度优先搜索），贪心之后，是一个极其高频的算法，牢记二分查找模板非常重要。

本人爆肝进行了模板全整理，目前力扣二分查找题全解正在进行中。

§ 模板介绍

$♠$ 模板一

模板简介

最经典的二分查找模板，教科书指定二分查找模板。

Binary Search Template I
二分查找模板 I

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) { 
            return mid; 
        } else if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    if (left != nums.size() && nums[left] == target) return left;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] <= target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }

    // End Condition: left > right
    if (right != -1 && nums[right] == target) return right;
    return -1;
}

区分语法

初始条件：left = 0, right = n - 1
循环条件：left <= right
向左查找：right = mid-1
向右查找：left = mid+1
mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左加右减，相错终止。

使用说明

二分查找的最基础和最基本的形式。
适合查找在所有元素均不相同的数组中查找某特定元素。

模板点评

母仪天下，福泽众生，鸾鸟朝凤，万世师表。

$♡$ 模板二

模板简介

Python中bisect源码实现模板，右边界可对应C++中end迭代器。

左闭右开的区间分割方式在数学和计算机中都极为普遍。

Binary Search Template II
二分查找模板 II

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size();
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) { 
            return mid; 
        } else if (nums[mid] < target) {
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.size() && nums[left] == target) return left;
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size();
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.size() && nums[left] == target) return left;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if(nums.size() == 0)
        return -1;

    int left = 0, right = nums.size();
    while(left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1; 
        } else { 
            right = mid; 
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(left != nums.size() && nums[left] == target) return left;
    if(left > 0 && nums[left - 1] == target) return left - 1;
    return -1;
}

区分语法

初始条件：left = 0, right = n
循环条件：left < right
向左查找：right = mid
向右查找：left = mid+1
mid指针计算：左右指针和折半向下取整

模板口诀

左闭右开，向下取整，左加右定，相等终止。

使用说明

二分查找的的高级方法。
查找条件需要访问元素的直接右邻居。
需要进行后处理。

模板点评

C_+.webp
凌波微步，罗袜生尘，才学雅量，识古通今。

$♣$ 模板三

模板简介

用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

Binary Search Template III
二分查找模板 III

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[right] == target) return right;
    if(nums[left] == target) return left;
    return -1;
}

区分语法

初始条件：left = 0, right = n - 1
循环条件：left + 1 < right
向左查找：right = mid
向右查找：left = mid
mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左定右定，相邻终止。

使用说明

二分查找的的高级方法。
用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
需要进行后处理。

模板点评

C#.webp
闺中女子，秀气英拔，兰质蕙心，左右逢源。

$♢$ 模板四

模板简介

ACM/ICPC大佬推荐查询目标元素左边界模板。

@acw_yxc Y总进行过很好的总结：二分查找算法模板，原链接被和谐了所以改用百度文库链接，实际上这是两套模板，本人这里进行拆分讲解。

将区间 [left,right] 二分为 [left,mid] 和 [mid+1,right]。

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left > 0 && nums[left - 1] == target) return left - 1;
    return -1;
}

区分语法

初始条件：left = 0, right = n - 1
循环条件：left < right
向左查找：right = mid
向右查找：left = mid + 1
mid指针计算：左右指针和折半向下取整

模板口诀

左闭右闭，向下取整，左加右定，相等终止。

使用说明

二分查找的的高级方法。
需要进行后处理。
注：在处理上下边界问题时，一般用模板四模板计算左边界。

模板点评

英姿飒爽，金刀映日，龙骧虎步，百战百胜。

$⧫$ 模板五

模板简介

ACM/ICPC大佬推荐查询目标元素右边界模板。

@acw_yxc Y总进行过很好的总结：二分查找算法模板，原链接被和谐了所以改用百度文库链接，实际上这是两套模板，本人这里进行拆分讲解。

将区间 [left,right] 二分为 [left,mid-1] 和 [mid,right]。

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] == target) {
                return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left + 1 < nums.size() && nums[left + 1] == target) return left + 1;
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    if(left + 1 < nums.size() && nums[left + 1] == target) return left + 1;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    // Post-processing:
    // End Condition: left == right
    if(nums[left] == target) return left;
    return -1;
}

区分语法

初始条件：left = 0, right = n - 1
循环条件：left < right
向左查找：right = mid - 1
向右查找：left = mid
mid指针计算：左右指针和折半向上取整

模板口诀

左闭右闭，向上取整，左定右减，相等终止。

使用说明

二分查找的的高级方法。
需要进行后处理。
注：在处理上下边界问题时，一般用模板五模板计算右边界。

模板点评

剑舞惊鸿，银剑对月，巾帼须眉，绝代双骄。

$★$ 模板六

模板简介

构造左右边界，蓝红二分，生动形象，界限分明。

蓝红二分法：蓝红二分法单模板秒杀二分查找

模板代码

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = -1, right = nums.size();
    while (left + 1 < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    return -1;
}

查找等于 $t a r g e t$ 的第一个元素下标，即查找 $t a r g e t$ 左边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = -1, right = nums.size();
    while (left + 1 < right) {
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(right != nums.size() && nums[right] == target) return right;
    return -1;
}

查找等于 $t a r g e t$ 的最后一个元素下标，即查找 $t a r g e t$ 右边界。

C++

Java

Python

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = -1, right = nums.size();
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(left != -1 && nums[left] == target) return left;
    return -1;
}

区分语法

初始条件：left = -1, right = n
循环条件：left + 1 < right
向左查找：right = mid
向右查找：left = mid
mid指针计算：左右指针和折半向下取整

模板口诀

左开右开，向下取整，左定右定，相邻终止。

使用说明

二分查找的的高级方法。
需要进行后处理。

模板点评

蓝红二分，百变魔女，天真烂漫，潜力无限。

§ 模板总结

当然二分查找还有一些别的模板，暂时没有收录，模板四和模板五是模板二的变体，模板六是模板三的变体，本质上都是二分思想的运用。

模板对比

每个模板的特征其实非常明显，共同点其实很多，我从两方面总结讲解帮助大家理解：

1.左右指针关系

左右指针关系	循环条件	优点	缺点	模板
相错终止	left <= right	可向两侧探索	探索到最后可能越界	一
相等终止	left < right	仅需向一侧探索	区间二分方式不同探索方向不同，探索到最后可能越界	二、四、五
相邻终止	left + 1 < right	只在二分后的界内活动，无需探索	后处理可能要检查两个指针	三、六

我们用图片来详细说明，根据 if else 二分判断条件，搜索区间一定能够进行二分，左边区域用蓝色标记，右边区域用红色标记，我们看下三种构造方式指针的起止状态变化：

相错终止时l指针会落在红色区域最左端，r指针落在蓝色区域最右端；
相等终止时两个指针一起落在蓝色区域最右端或者红色区域最左端；
相邻终止时l指针会落在蓝色区域最右端，r指针落在红色区域最左端。
相邻终止的好处是两个指针所属区域非常分明，不会越界。

2.初始区间选择

| 初始区间选择 | 优点 | 缺点 | 模板 |
| :-----: | :-----: | :-----: | :-----: | :-----: |
| 左闭右闭 | 指针所指向元素不会越界 | 指针所指向元素不一定是答案，要进行后处理 | 一、三、四、五 |
| 左闭右开 | 构造右边界，方便右侧越界情况处理，同时区间连续性符合数学思维 | 指针所指向元素会越界 | 二 |
| 左开右开 | 构造左右边界，方便两侧越界情况处理 | 指针所指向元素会越界 | 六 |

其实我们并不能保证已知搜索区间蓝色或者红色区域长度大于0，这时候可以构造边界，就是开区间，可以增加左边界变为左开右闭，增加右边界变为左闭右开，增加两侧边界变为左开右开。

提供一个本人构造边界的思路：

二分查找的结果不一定存在，这时候有可能不是在第一个元素左侧就是在最后一个元素右侧，这时候就要构造边界，就是开区间，开区间有三种开法，左开右闭，左闭右开，左开右开，左开右开是双保险，我们明确知道缺失元素位于哪一侧其实只要开单侧就行。

如果不构造边界可能产生冲突需要后处理中进行判断。

关于构造边界，其实是一个非常常见的技巧，除了在数组中出现，单调栈，单链表等我们也可以看到它的身影。

补充一下，每套模板的优缺点都很明显，目前不存在一个只有优点没有缺点的模板，每套模板的普适性都很高，不存在只用一套模板就不能解题的情况，我们觉得用哪套模板解题更优秀其实区别在于后处理复杂程度，比如模板四找左边界的代码明显比模板五找左边界的代码更加简洁，但模板五找右边界的代码明显比模板四找右边界的代码更加简洁，才会出现两个模板组合使用的情况。有些同学希望换个模板就能解决问题那是本末倒置了。

二分查找最难的地方在于二分，不在查找！

如果开始二分建模就错了，无论套哪个模板大概率无法查找到正确答案，如何二分建模是同学们要通过做题自己体悟的。
二分就是那个if判断条件啊，你发现这个是没办法模板化的。
我们发现，所有模板的二分方案惊人的一致。

模板构造

总共有多少种二分查找模板？

以下为本人的一点研究发现：

相错终止or相等终止or相邻终止
共计3种构造方式。
左闭右闭or左开右闭or左闭右开or左开右开
共计4种构造方式。
向上取整or向下取整
就是每次二分取下中位数点还是上中位数点进行分割，这个和相等终止联系最紧密，就是在蓝色区域最右侧或在红色区域最左侧终止，模板四和模板五中有很好体现，官方常用二分查找模板。
共计2种构造方式。
根据乘法原理合计24种构造方式，也就是我们一定能写出24种二分查找模板。

这24种模板我就不一一写代码说明了，直接枚举代码口诀如下：

左闭右闭，向下取整，左加右减，相错终止。（模板一）
左闭右开，向下取整，左加右减，相错终止。
左开右闭，向下取整，左加右减，相错终止。
左开右开，向下取整，左加右减，相错终止。
左闭右闭，向上取整，左加右减，相错终止。
左闭右开，向上取整，左加右减，相错终止。
左开右闭，向上取整，左加右减，相错终止。
左开右开，向上取整，左加右减，相错终止。

左闭右闭，向下取整，左加右定，相等终止。（模板四）
左闭右开，向下取整，左加右定，相等终止。（模板二）
左开右闭，向下取整，左加右定，相等终止。
左开右开，向下取整，左加右定，相等终止。
左闭右闭，向上取整，左定右减，相等终止。（模板五）
左闭右开，向上取整，左定右减，相等终止。
左开右闭，向上取整，左定右减，相等终止。
左开右开，向上取整，左定右减，相等终止。

左闭右闭，向下取整，左定右定，相邻终止。（模板三）
左闭右开，向下取整，左定右定，相邻终止。
左开右闭，向下取整，左定右定，相邻终止。
左开右开，向下取整，左定右定，相邻终止。（模板六）
左闭右闭，向上取整，左定右定，相邻终止。
左闭右开，向上取整，左定右定，相邻终止。
左开右闭，向上取整，左定右定，相邻终止。
左开右开，向上取整，左定右定，相邻终止。

构造解析

后来又仔细研究了下，发现指针关系和运行和区间开闭有强相关：
我简单说明下原因，后一次二分查找区间 $\subset$ 当前二分查找区间，也就是搜索区间要不断缩小才能夹逼出目标元素。
所以有这样的推导过程：
左闭右闭 $\Leftrightarrow$ 左加右减 $\Leftrightarrow$ 相错终止；
左闭右开 $\Leftrightarrow$ 向下取整，左加右定 $\Leftrightarrow$ 相等终止；
左开右闭 $\Leftrightarrow$ 向上取整，左定右减 $\Leftrightarrow$ 相等终止；
左开右开 $\Leftrightarrow$ 左定右定 $\Leftrightarrow$ 相邻终止；

我们要掌握其中两关键点：
① 指针与其负责区间强绑定： $l$ 负责左边红色区域， $r$ 指针负责右边蓝色区域。
② 指针 $c h ec k$ （即模板中的 $i f$ 判定函数）的元素必须为区间内的有效元素
思路一：由中心向两端扩散，从终止态回推初始态。
相错终止， $l$ 和 $r$ 指针都处于负责区间外，处于湮灭状态， $l = l - 1, r = r + 1$ 才能恢复到有效区间，二分查找模板是从两端向中心扩散，所以指针运行反过来， $l = l + 1, r = r - 1$ ，正好对应左加右减。
相等终止，情况一， $l$ 和 $r$ 指针都位于红色区域， $l$ 指针都处于负责区间外，处于湮灭状态， $l = l - 1$ 才能恢复到有效区间，二分查找模板是从两端向中心扩散，所以指针运行反过来， $l = l + 1$ ， $r$ 已经位于有效区域，无需移动，正好对应左加右定。
相等终止，情况二， $l$ 和 $r$ 指针都位于蓝色区域， $r$ 指针都处于负责区间外，处于湮灭状态， $r = r + 1$ 才能恢复到有效区间，二分查找模板是从两端向中心扩散，所以指针运行反过来， $r = r - 1$ ， $l$ 已经位于有效区域，无需移动，正好对应左定右减。
相邻终止， $l$ 和 $r$ 已经位于有效区域，无需移动，正好对应左定右定。
思路二：由两端向中心扩散，从初始态态正推终止态。
左闭右闭： $l$ 和 $r$ 指针都处于有效位置，为了探索新的有效位置， $l$ 和 $r$ 指针都必须进行移动，而且是向中心靠拢， $l = l + 1, r = r - 1$ ，正好对应左加右减。
左闭右开： $l$ 指针处于有效位置，为了探索新的有效位置， $l$ 指针都必须进行移动，而且是向中心靠拢， $l = l + 1$ ，正好对应左加右定。
左开右闭： $r$ 指针处于有效位置，为了探索新的有效位置， $r$ 指针都必须进行移动，而且是向中心靠拢， $r = r - 1$ ，正好对应左定右减。
左开右开：两个指针都不处在有效位置，通过变成 $mi d$ 指针进行移动，正好对应左定右定。

还有一个问题，为什么指针每次移动只能移动一格，你确定能不负责的跳过判定移动好几个格子？

到此为止，逻辑整个都打通了！

另外，本人研究发现：
闭区间转开区间会在循环中增加 $mi d$ 指针中间处理，本质是增加了指针区域，并没有增加有效元素区域带来的问题；
开区间转闭区间只会增加循环结束后的 $l$ 指针或 $r$ 指针处理。当然，开区间转闭区间好处就是全程不会访问越界，缺点就是会导致原来的开区间指针移位了，后处理中要增加额外判断。

所以删除闭区间转开区间的10种模板，留下比较合理的下面这14种：

左闭右闭，向下取整，左加右减，相错终止。（模板一）
左闭右闭，向上取整，左加右减，相错终止。

左闭右闭，向下取整，左加右定，相等终止。（模板四）
左闭右开，向下取整，左加右定，相等终止。（模板二）
左闭右闭，向上取整，左定右减，相等终止。（模板五）
左开右闭，向上取整，左定右减，相等终止。

当然核心的就6种，可以说是最合理的二分查找模板：

左闭右闭，向下取整，左加右减，相错终止。（模板一）
左闭右闭，向上取整，左加右减，相错终止。

左闭右开，向下取整，左加右定，相等终止。（模板二）
左开右闭，向上取整，左定右减，相等终止。

左开右开，向下取整，左定右定，相邻终止。（模板六）
左开右开，向上取整，左定右定，相邻终止。

模板一二三只是其中的典型，掌握其中核心思路就能按照题目场景自由选择模板了。

如果有同学能够创造出新的模板构造因素，欢迎留言或者私信，我一定补上并推广！

模板推荐

关于现在用哪个模板，主流是：
模板一：教科书指定无需多言，正式考试如考研推荐使用。
模板四 组合 模板五 ：非常方便且满足竞赛需要。
我们的 Y总 @acw_yxc 和三叶姐 @AC_OIer 都特别喜欢模板四 组合 模板五，大佬们都是刀山火海过来的，模板四 组合 模板五的强大是受过检验的。

此外，模板六蓝红二分法给我们提供了一个非常好的新思路，实现了二分的具体化，而且相比模板一二三四五之类的传统二分法，蓝红二分法的优点非常多，除了指针所指向元素会越界需要单独处理，其他则省去了很多特殊情况判断，用了你就会明白，甚至我觉得蓝红二分法就是二分查找模板的终极方案。

解题步骤

二分查找解题三步走：
第一步：构造区间，二分建模
第二步：套用二分查找模板
第三步：后处理求出答案

高级接口

一些语言也提供了一些二分查找的高级api：

语言	查找目标元素	查询第一个大于等于目标元素的元素	查询第一个大于目标元素的元素
C++	binary_search	lower_bound	upper_bound
Java	binarySearch
Python	bisect	bisect_left	bisect_right
Java 没有查询左右边界api，主 Java 的同学必须要用模板了。

§ 模板投票

六款二分查找模板，哪款才是你的菜？投票活动。
这可是选你最喜欢的二分查找女友啊！
欢迎大家积极参与，到月底投票结束后也会把结果进行公布。

投票应该已经超时了，也没有几票，我语文水平不好，文案写的糟糕请见谅，大家就图个乐子吧。

其实二分查找模板不是最重要的，二分建模思路才是核心。

微信手机端投票入口：二分查找模板投票
B站手机端投票入口：二分查找模板投票
本人已向力扣提出增加投票功能建议，力扣小编已采纳，非常期待这一功能将来能够上线！

这边临时借用其它网站，如果大家觉得不方便也欢迎留言评论发表观点。

如果文章内容有问题也请大家批评指正，我一定虚心采纳！
如果有更好的二分查找模板也可留言推荐！
欢迎大家积极讨论！
感谢阅读！

§ 前言

§ 算法简介

§ 模板介绍

♠ 模板一

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

♡ 模板二

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

♣ 模板三

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

♢ 模板四

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

⧫ 模板五

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

★ 模板六

模板简介

模板代码

区分语法

模板口诀

使用说明

模板点评

§ 模板总结

模板对比

模板构造

构造解析

模板推荐

解题步骤

高级接口

§ 模板投票

$♠$ 模板一

$♡$ 模板二

$♣$ 模板三

$♢$ 模板四

$⧫$ 模板五

$★$ 模板六