警告：该二分算法有一定的局限性，只能解决“在数组中查找特定值的元素问题”。对于“查找特定边界”类的问题有些束手无策，例如：数的范围。
关于更优秀的二分算法模板，可以看我最新的文章：[AcWing]二分算法

本篇算法内容基于 LeetCode 704: 二分查找

本文内容默认你已经对二分算法有一定的了解，这里不做过多算法流程的介绍，只介绍一些必要的处理细节以帮助你更好的理解二分算法。如果，你是刚刚接触二分算法，请先自行学习二分算法的基本流程。

一、基于左闭右闭区间

首先，我们需要明确的一点是——在左闭右闭区间（即 [Left, Right] 区间）范围内，包括 Left 与 Right 的值在搜索区间内。对于例如 [1, 1] 的区间属于合法区间范围，可以被遍历。下面是完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int middle = left + (right - left) / 2;

            if (nums[middle] < target)
            {
                left = middle + 1;
            }
            else if (nums[middle] > target)
            {
                right = middle - 1;
            }
            else
            {
                return middle;
            }
        }

        return -1;
    }
};

1.1 初始化赋初值

1
2
int left = 0;
int right = nums.size() - 1;

为什么 right 被初始化为 nums.size() - 1 而不是 nums.size() 呢？因为我们的搜索区间是一个左闭右闭的区间，也就是搜索区间会包括左边界值和右边界值。所以，初始搜索范围应该是从数组的第一个元素一直到数组的最后一个元素并包括数组第一个元素和数组最后一个元素在内的区间。

1.2 循环结束判定条件

1
while (left <= right)

为什么 left <= right 而不是 left < right 呢？这很容易想清楚！因为形如 [1, 1] 的区间也是一个合法区间，既然是合法区间就应该继续执行搜索直到搜索完成。

1.3 区间收缩处理

1
2
3
4
5
6
7
8
9
10
11
12
if (nums[middle] < target)
{
    left = middle + 1;
}
else if (nums[middle] > target)
{
    right = middle - 1;
}
else
{
    return middle;
}

当 target 在 middle 的右边（即 nums[middle] < target）时，我们应该把区间的左边进行收缩，从而减少搜索范围。
图1.3.1 左收缩

当 target 在 middle 的左边（即 nums[middle] > target）时，我们应该把区间的右边进行收缩，从而减少搜索范围。
图1.3.2 右收缩

当 target 为 middle 的值（即 nums[middle] == target）时，我们就找到了目标值，便可以直接返回该值所在坐标 middle。
图1.3.3 找到值

1.3.1 左收缩

1
left = middle + 1;

为什么 left 等于 middle + 1 而不是 middle 呢？因为在左闭区间内是包括左边界值的，如果我们使 left = middle，那就相当于我们已经知道 nums[middle] < target 的事实，却还要将 nums[middle] 纳入下一次搜索区间继续搜索。但实际上，如果我们已经知道了 nums[middle] < target，那么我们就完全没必要再搜索 nums[middle] 了，所以我们可以直接使 left = middle + 1 而在下一次循环中忽略 nums[middle]。

1.3.2 右收缩

1
right = middle - 1;

为什么 right 等于 middle - 1 而不是 middle 呢？因为在右闭区间内是包括右边界值的，我们没必要在下一次搜索区间内包括 nums[middle]，所以可以直接使 right = middle - 1 而在下一次循环中忽略 nums[middle]。

二、基于左闭右开区间

首先，我们需要明确的一点是——在左闭右开区间（即 [Left, Right) 区间）范围内，包括 Left 的值，但是不包括 Right 的值在搜索区间内。对于例如 [1, 1) 的区间属于非法区间范围，是不可以被遍历的。下面是完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();

        while (left < right)
        {
            int middle = left + (right - left) / 2;

            if (nums[middle] < target)
            {
                left = middle + 1;
            }
            else if (nums[middle] > target)
            {
                right = middle;
            }
            else
            {
                return middle;
            }
        }

        return -1;
    }
};

2.1 初始化赋初值

1
2
int left = 0;
int right = nums.size();

为什么 right 应该被初始化为 nums.size() 而不是 nums.size() - 1 呢？因为我们是基于左闭右开区间的，右边界值是不在区间范围内的。而 nums[nums.size() - 1] 是初始搜索区间范围的右边界值，它应该被包括在第一次搜索范围内。

2.2 循环结束判定条件

1
while (left < right)

为什么使用 left < right 作为判断条件而不包括 left == right 的情况在内？这是因为形如 [1, 1) 的区间是一个非法区间，左边界告诉我们要包括数值 1，但是右边界告诉我们不能包含数值 1，那么就会产生矛盾。而一个非法搜索区间应该被继续搜索吗？我想答案是显然的。

2.3 区间收缩处理

1
2
3
4
5
6
7
8
9
10
11
12
if (nums[middle] < target)
{
    left = middle + 1;
}
else if (nums[middle] > target)
{
    right = middle;
}
else
{
    return middle;
}

前面已经叙述过这个代码流程的逻辑，需要的可以看 1.3 区间收缩处理的内容。

2.3.1 左收缩

1
left = middle + 1;

前面已经叙述过，这里不做赘述，需要的可以看 1.3.1 左收缩的内容。

2.3.2 右收缩

1
right = middle;

为什么 right 被赋值为 middle 而不是 middle - 1 呢？道理还是那个道理，右开区间不包括右边界值，所以使 right 等于 middle 就已经将 nums[middle] 排除在下一次搜索范围之外了。

三、基于左开右闭区间

一般不会这么做，真的要这么做记得处理好 left 的初始化操作和以上列举的细节。