二分查找主要是通过分治法来实现对数时间复杂度的查找，二分查找的写法很多，但一般可分为三种：相错终止、相等终止、相邻终止。
0. 三个基本模板
模板一 相错终止
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
模板二 相等终止
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid;
}
return -1;
模板三 相邻终止
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid;
else r = mid;
}
return -1;
二分查找的写法很多，细节也很繁杂，但实际上只要注意下面几个要素就能确定一个二分查找算法的效用。
1. 终止条件是什么？
终止条件即跳出循环的条件，这个一般是由 While 语句的所决定的。
模板一的终止条件是 L = R + 1
模板二的终止条件是 L = R
模板三的终止条件是 L + 1 = R
这是上述三个模板的主要区别，它决定了算法循环结束后 L 和 R 的相对位置。
2. 终止位置有什么意义？
也就是说，我们要确定结束时 L 和 R 位置的元素满足什么条件。以模板一为例：
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
根据循环中的代码，如果找到了 target，那么程序不会跳出循环，而是直接返回。如果没有找到 target，跳出循环时由终止条件即 L = R + 1
并且在循环中，由于 L = mid + 1 以及 R = mid – 1，保证了 L 前面的元素（不包括 L 本身）总是小于 target ，而 R 后面的元素（不包括 R 本身）总是大于 target ，于是我们可以确定如下图的终止情形：
这表明，终止位置的意义是 R 处在最后一个小于 target 的位置，L 处在第一个大于 target 的位置，这两个位置分别称为刚好小于位置和刚好大于位置。
对模板一（模板二、模板三）都可以进行稍加变形，即改变循环中的条件，最终会改变终止位置的意义，从而获得自己想要的信息。比如：
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
else if(nums[mid] <= target) l = mid + 1;
else r = mid - 1;
}
终止条件是不变的，依旧是 L = R + 1
但是循环中的代码改变了，我们此时只能保证 L 前面的元素（不包括 L 本身）总是小于等于 target ，而 R 后面的元素（不包括 R 本身）总是大于 target，于是我们得到如下图的终止情形：
这意味着，L 依旧是刚好大于位置，但 R 有两种可能，要么所在元素就是 target，要么就是刚好小于位置。所以跳出循环后，我们需要进一步判断以确定 R 位置的元素。
对于模板二、模板三都是同理的，区别只在于终止条件不同，故最终 L 和 R 的相对位置也不同。
以模板二的一个变形为例：
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
else if(nums[mid] < target) l = mid + 1;
else r = mid;
}
根据终止条件 L = R 以及循环内的代码，我们可以得到如下图的终止情形：
这时有两种可能，即要么 L/R 所在元素就是 target，要么 L/R 是刚好大于位置。
模板三的分析也一样，区别只是它的终止条件为 L + 1 = R
以模板三的一个变形为例：
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] < x) l = mid;
else r = mid;
}
跳出循环后，我们可以得到如下情形：
这个时候 L 为刚好小于位置，而 R 需要进一步判断。
总之，通过代码分析，我们可以确定终止位置的意义，这样根据问题的需要可以自由选择，并且多个模板的多个写法之间存在重合，有些时候都能解决问题。
3. 特殊情况如何处理？
上面所说的都是一般情况下，算法所满足的性质，但有些时候由于数据的特殊性，我们可能会遇到特殊的情况。二分查找要考虑的细节便在这些特殊情况之中。
在上述三个模板中，特殊情况主要是由 L 和 R 的初始值所决定的。对任何一个二分查找算法，我们主要考虑以下几种特殊情况：
- 查找的元素大于数组中所有元素
- 查找的元素小于数组中所有元素
- 数组中仅有一个元素
- 数组中仅有两个元素
基本上三个模板及其变形都会在上面四种情况中的一两种出现问题，事实上，任何简练的模板都不可能兼容所有特殊情况。
这些特殊情况集中在两个问题，第一个问题就是 L 或 R 可能有一个至始至终都未更新，即循环结束时它依旧还是初始值，如果初始值本身就是越界的那么它就有问题了，可能不再具备正确的位置意义。第二个问题就是使用了有关 L 或 R 的下标，但没有考虑到 L 和 R 在特殊情况下会导致下标越界，特别是在数组元素只有一个或两个元素时对下标进行运算的风险很大。
什么情况下 L 或 R 可能有一个不变呢？那就是查找的元素大于或小于所有元素时。
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
对模板一，L 和 R 的初始值都是界内值，如果目标值大于所有元素或者小于所有元素，退出循环时 L = R + 1 = nums.Length 或 L = R + 1 = 0，此时 L 和 R 必定有一个越界了，而另一个依旧会处在刚好大于位置或刚好小于位置。
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid;
}
return -1;
对模板二，R 的初始值已经越界，如果目标值大于所有元素，那么退出循环时有 L = R = nums.Length，此时两个都越界了，但依旧能断言 target 不存在。
当然，这里为什么要把 R 的初始值设置为 nums.Length 呢？其实是为了保证程序能够区分出特殊情况，如上所说，如果退出循环时 R = nums.Length，我们可以断言 target 大于所有元素。如果将 R 的初始值设置为 R = nums.Length – 1，那么如果退出循环时 R = nums.Length – 1，我们无法确定是因为 target 大于所有元素还是最后一个元素就是 target。
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid;
else r = mid;
}
对于模板三，L 和 R 的初始值均越界，存在 L + 1 = R = nums.Length 以及 L + 1 = R = 0 两种情况，此时必定有一个越界了，而另一个依旧会给出正确的位置意义。
上面只是列举了三个模板最简单的越界情况，对于三个模板的变形（循环体内改为大于、大于等于、小于、小于等于），各自会有其越界情形。面对一个具体问题时，我们最好对可能的特殊情况都进行验证，这是最笨的办法，却也是最高效的。
4. 如何选择使用哪个模板？
实际上考虑每个模板的变形在内，很多问题都可以使用多个模板来解决，因为它们都能表达相同的逻辑，区别只在于退出时 L 和 R 位置意义和特殊情况的不同。关键是对问题和代码的分析，之后也只是看个人习惯而已。
