前言

二分查找，是算法领域的一类经典题目，也是很多人非常头疼的一种算法。市面上很多文章，都是罗列了大量不同类型的经典例题以及对应的代码，从而解释如何撰写二分查找。而本文会从二分查找的原理出发，为大家解读二分查找的难点在哪，核心思路是什么，通过了解底层原理的方式，帮助大家解开二分查找这一大类的题目，而不只是会写某些经典的例题。

什么情况可以使用二分查找

凡是在有序序列中查找某个值（某个位置），都可以往二分查找的方向去思考。所以，二分查找可以被应用的充分条件，就是序列有序。

二分查找的难点在哪

我们用一道例题来看一个经典二分查找的模板：

leetCode 35:给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

leetcode.cn/problems/se…

解法如下

func binarySearch(arr []int, target int) int {
   var low, high = 0, len(arr) - 1
   for low <= high {
      mid := low + (high-low)/2
      if arr[mid] >= target {
         high = mid - 1
      } else {
         low = mid + 1
      }
   }
   return high + 1
}

我们通过以上代码即可解开本题。本题的解法也是最常规的二分查找的模板，各种二分查找的写法，都和上述模板相差不多。

那么模板相对简单的情况下，这类题的难点是什么呢？

总结一下，难点，有如下几个。

1. low，high的初始值如何定义？为什么low的初始值有时定义为0，有时为-1？为什么high的初始值有时候定义为len(arr) - 1, 有时候定义为len(arr)？
2. for循环的条件如何写？究竟是low < high，还是low <= high？
3. for循环体中if else处到底怎么写，比较符号符号到底是大于（小于），还是大于等于（小于等于）？high和low每次改变位置时到底怎么变化，是 high(low) = mid， 还是high(low) = mid - 1(+ 1)?
4. 最终的返回值怎么写，返回high还是low，-1还是+1？

func binarySearch(arr []int, target int) int {
/*
low，high的初始值如何定义？为什么low的初始值有时定义为0，有时为-1？为什么high的初始值有时候定义为len(arr) - 1, 有时候定义为len(arr)？
*/
   var low, high = 0, len(arr) - 1
   
/*
for循环的条件如何写？究竟是小于等于，还是小于？
*/
   for low <= high {
      mid := low + (high-low)/2
      
/*
if else处到底怎么写，符号到底是大于/小于，还是大于等于/小于等于？high和low每次改变位置时到底怎么变化，是 high（low） = mid， 还是high(low) = mid - 1(+ 1)?
*/
      if arr[mid] >= target {
         high = mid - 1
      } else {
         low = mid + 1
      }
   }

/*
最终返回值怎么写？
*/
   return high + 1
}

这几个难点，不仅是我，也是我身边的同学和同事最初学习二分查找时所遭遇的难点，由于这些难点，经常造成所写出来的算法出现 无限循环，指针越界，返回值错误 等问题。

二分查找的核心思路

本质

二分查找的本质，可以这么描述：最终目的是在一串有序数组中，寻找某个特定的值/位置。

二分查找模板解读

二分查找算法定义了两个指针，指向数组的两端。指针内侧的数组，代表“没有被检索”的数组；指针左右两侧的数组，代表“已经被检索过”的数组，目标值不可能在指针外侧。我们每次通过和“未检索数组”最中间的元素做比较，每次比较即可排除剩余一半的数组长度，直到“整个数组检索完毕”，即可明确是否找到特定的值。

攻破二分查找的难点

low和high初始值怎么定义

初始时，整个数组未被检索，我们采用“区间”来描述这一概念。low和high指针指向的位置是区间的两端，区间内的元素，代表“未被检索”的元素。我们定义low指向0，high指向len(arr) - 1。这是一个闭区间的写法，代表着[0,len(arr)-1]的位置均未被检索。后续还会介绍“半闭半开”，“开区间”的写法。

for循环条件怎么写

因为写法是闭区间写法，所以只要low <= high时，两指针之间依然还有元素未被检索。故写成low <= high。直到high < low时，两指针内部的元素才全部被检索完。

if else怎么写

这里的概念，即是二分查找的一个核心概念：循环不变式。

我们定义，在for循环不断执行的过程中，high指针的右侧数据，全部严格大于等于target；low指针左边的数据，全部严格小于target，直到全部元素被检索完毕。

每次和arr[mid]比较时，若发现arr[mid]大于等于target，即表示mid和mid右侧的全部数据均大于等于target，为了满足循环不变式，high需要置为mid - 1； 反之即表示arr[mid]小于target，为了满足循环不变式，low需要置为mid + 1。

所以关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质。 这个循环不变式，是贯穿整个查找过程的。我们在写代码的时候，一定要把握住循环不变式。

返回值怎么写

最终，整个数组检索完毕，由循环不变式可知，high右侧的元素均严格大于等于target，所以如果数组中有某个值等于target，它的位置是high + 1，如果没有值等于target，那么target需要被插入的位置也是high + 1。所以返回high + 1。

当然，根据循环不变式，当循环结束时，low指针左侧的全部数据严格小于target，所以low指针本身指向的位置，也可以作为返回值。

模板的灵活变形

上述的整体介绍，都是按照“闭区间”的思路进行的。我们也可以按照“左闭右开”，“左开右闭”，“开区间”的思路去完成上述题目。

左闭右开

初始值定义：因为右侧是开区间，所以high指针需要指向len(arr)，从而表示整个数组均未被检索。我们定义low初始值为0，high初始值为len(arr)。即[0, len(arr) )表示初始整个未检索的数组。

for循环条件：当low < high时，表示两指针所表示的区间内依然有未被检索的元素。

if else怎么写：此时的循环不变式即为：high以及high的右侧数据全部严格大于等于target，low左边的数据全部严格小于target（注意和闭区间的循环不变式的区别）。所以写法应为：

if arr[mid] >= target {
   high = mid
} else {
   low = mid + 1
}

返回值怎么写：依据循环不变式，high指针的位置即为返回值；同样，也可以返回low。

所以最终的写法为：

func binarySearch(arr []int, target int) int {
   var low, high = 0, len(arr)
   for low < high {
      mid := low + (high-low)/2
      if arr[mid] >= target {
         high = mid
      } else {
         low = mid + 1
      }
   }
   return high
}

左开右闭

和左闭右开的分析思路非常相似，我们可以写出如下代码

func binarySearch(arr []int, target int) int {
   var low, high = -1, len(arr) - 1
   for low < high {
      mid := low + (high-low+1)/2
      if arr[mid] >= target {
         high = mid - 1
      } else {
         low = mid
      }
   }
   return high + 1
   // 也可以return low + 1
}

开区间

同样的分析思路，开区间的写法如下

func binarySearch(arr []int, target int) int {
   var low, high = -1, len(arr)
   for low < high-1 {
      mid := (low + high) / 2
      if arr[mid] >= target {
         high = mid
      } else {
         low = mid
      }
   }
   return high
}

特殊情况解读

不知道大家有无注意到，左开右闭写法，在计算mid位置的时候，和别的写法不同，有一处额外的 +1，这是为什么呢？

二分查找的思路，就是用两个指针，从左右两侧，不断地逼近要寻找的值。

而逼近的方法，就是每次和两个指针中间位置的数做比较。即low + (high - low) / 2

但是，常见的go，c++等语言，会有一个天然的性质，即向下整除。在二分查找中，如果偶数和奇数相加并除以二，结果会自动扔掉小数部分。我们认为，这种特性，使得两个整数相除，会使得结果有可能“偏小”。

在左开右闭的写法中，low指针每次的变化，是 low = mid，而不是low = mid + 1。

low指针的变化规则，加上忽略小数部分的特性，会导致一种特殊情况：如果待查找的值，就是递增数组最右侧的值，此时我们如果按照 mid = low + (high - low) / 2 的写法，会发生无限循环。即，结果“偏小”的特性，加之左开右闭的写法，使得mid指针没法继续向右移动了。

举个例子

arr = [1,2,3,4] , 待查找的target = 4

初始low = -1，high = 3，最终会卡在low = 2, high = 3处无限循环。 这就是上述问题造成的结果。

所以，我们每次有一个 “+1” 的操作，造成的效果如下：

1. 当low + high = ans的结果为偶数时， +1之后ans为奇数，除以二所得结果并没有任何改变。
2. 当low + high = ans的结果为奇数时， +1之后ans为偶数，除以二所得结果会比原值+1。 这个+1，会使得mid的位置额外向右移动一格，可以完美的解决上述问题。同时将mid右移或左移一格并不会对二分查找造成任何影响（我原先是每次和最中间的数做比较，现在是和最中间的数右边的数做比较，对于时间复杂度和正确性都不会有任何影响）。

其余三种写法，要么low指针的变化方式为 low = mid + 1，要么循环不结束的条件为low + 1 < high，均破坏了可能造成无限循环的条件。

总结

我们想要彻底理解透二分查找，就是要理解透上述罗列的难点该如何解。我们把二分查找抽象成两个指针一左一右不断逼近答案，在逼近的过程中理解清楚开闭区间，循环不变式，即是二分查找的核心。在核心思路之上同时灵活地做一些变形，加之不断的练习，即可完美的解决所有二分查找的题目。