店小二：掌柜的，您进货回来了呀，哟！今天您买这鱼挺大呀！袁厨：那是，这是我今天从咱们江边买的，之前一直去菜市场买，那里的老贵了，你猜猜我今天买的多少钱一条。店小二：之前的鱼，30 个铜板一条，今天的我猜 26 个铜板。袁厨：贵了。店小二：还贵呀！那我猜 20 个铜板！袁厨：还是贵了。店小二：15 个铜板。袁厨：便宜了店小二：18 个铜板袁厨：恭喜你猜对了
上面的例子就用到了我们的二分查找思想，如果你玩过类似的游戏，那二分查找理解起来肯定很轻松啦。
二分查找
二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。通过上面二分查找的定义，我们知道了二分查找算法的作用及要求，那么该算法的具体执行过程是怎样的呢？下面我们通过一个例子来帮助我们理解。我们需要在 nums 数组中，查询元素 8 的索引。
-
找出 mid，该索引为 mid =（left + right）/ 2，但是这样写有可能溢出，所以我们需要改进一下写成 mid = left +（right - left）/ 2 或者 left + ((right - left ) >> 1) 两者作用是一样的，都是为了找到两指针的中间索引，使用位运算的速度更快。那么此时的 mid = 0 + (8-0) / 2 = 4图片
二分查找的执行过程如下
****二分查找的执行过程如下****
从已经排好序的数组或区间中，取出中间位置的元素，将其与我们的目标值进行比较，判断是否相等，如果相等则返回。
如果 nums[mid] 和 target 不相等，则对 nums[mid] 和 target 值进行比较大小，通过比较结果决定是从 mid的左半部分还是右半部分继续搜索。
如果 target > nums[mid] 则右半区间继续进行搜索，即 left = mid + 1; 若target < nums[mid] 则在左半区间继续进行搜索，即 right = mid -1；动图解析
二分查找的思路及代码已经理解了，那么我们来看一下实现时容易出错的地方。 易错点：
计算 mid 时 ，不能使用 （left + right ）/ 2，否则有可能会导致溢出
while (left < = right)，注意括号内为 left <= right ，而不是 left < right ，我们继续回顾刚才的例子，如果我们设置条件为 left < right 则当我们执行到最后一步时，则我们的 left 和 right 重叠时，则会跳出循环，返回 -1，区间内不存在该元素，但是不是这样的，我们的 left 和 right 此时指向的就是我们的目标元素 ，但是此时 left = right 跳出循环
left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。我们思考一下这种情况,见下图，当我们的target 元素为 16 时，然后我们此时 left = 7 ，right = 8，mid = left + (right - left) = 7 + (8-7) = 7，那如果设置 left = mid 的话，则会进入死循环，mid 值一直为7 。
下面我们来看一下二分查找的递归写法
例题及解析
例题：
题目来源：leetcode35 搜索插入位置 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例 1:
输入: [1,3,5,6], 5 输出: 2
示例 2:
输入: [1,3,5,6], 2 输出: 1
示例 3:
输入: [1,3,5,6], 7 输出: 4
示例 4:
输入: [1,3,5,6], 0 输出: 0
题目解析
这个题目完全就和咱们的二分查找一样，只不过有了一点改写，那就是将咱们的返回值改成了 left，具体实现过程见下图二分查找变种一
上面我们说了如何使用二分查找在数组或区间里查出特定值的索引位置。但是我们刚才数组里面都没有重复值，查到返回即可，那么我们思考一下下面这种情况：此时我们数组里含有多个 5 ，我们查询是否含有 5 可以很容易查到，但是我们想获取第一个 5 和 最后一个 5 的位置应该怎么实现呢？哦！我们可以使用遍历，当查询到第一个 5 时，我们设立一个指针进行定位，然后到达最后一个 5 时返回，这样我们就能求的第一个和最后一个五了？因为我们这个文章的主题就是二分查找，我们可不可以用二分查找来实现呢？当然是可以的。
题目描述
题目来源：leetcode 34 在排序数组中查找元素的第一个和最后一个位置给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
题目解析
这个题目很容易理解，我们在上面说了如何使用遍历解决该题，但是这个题目的目的就是让我们使用二分查找，我们来逐个分析，先找出目标元素的下边界，那么我们如何找到目标元素的下边界呢？我们来重点分析一下刚才二分查找中的这段代码其实原理很简单，就是我们将小于和等于合并在一起处理，当 target <= nums[mid] 时，我们都移动右指针，也就是 right = mid -1，还有一个需要注意的就是，我们计算下边界时最后的返回值为 left ，当上图结束循环时，left = 3，right = 2，返回 left 刚好时我们的下边界。我们来看一下求下边界的具体执行过程。动图解析
二分查找变种二
我们在上面的变种中，描述了如何找出目标元素在数组中的上下边界，然后我们下面来看一个新的变种，如何从数组或区间中找出第一个大于或最后一个小于目标元素的数的索引，例 nums = {1,3,5,5,6,6,8,9,11} 我们希望找出第一个大于 5的元素的索引，那我们需要返回 4 ，因为 5 的后面为 6，第一个 6 的索引为 4，如果希望找出最后一个小于 6 的元素，那我们则会返回 3 ，因为 6 的前面为 5 最后一个 5 的索引为 3。题目我们已经了解，下面我们先来看一下如何在数组或区间中找出第一个大于目标元素的数吧。找出第一个大于目标元素的数，大概有以下几种情况数组包含目标元素，找出在他后面的第一个元素；
目标元素不在数组中，且数组中的所有元素都大于它，那么我们此时返回数组的第一个元素即可；
目标元素不在数组中，数组内的部分元素大于它，此时我们需要返回第一个大于他的元素；
目标元素不在数组中，且数组中的所有元素都小于它，那么我们此时没有查询到，返回 -1 即可。
既然我们已经分析完所有情况，那么这个题目对咱们就没有难度了，下面我们描述一下案例的执行过程
上面的例子中，我们需要找出第一个大于 7 的数，那么我们的程序是如何执行的呢？上面的例子我们已经弄懂了，那么我们看一下，当 target = 0时，程序应该怎么执行呢？nums = {1,3,5,5,6,6,8,9,11} target = 7
通过上面的例子我们应该可以完全理解了那个变种。下面我们继续来看以下这种情况，那就是如何找到最后一个小于目标数的元素。还是上面那个例子
查找最后一个小于目标数的元素，比如我们的目标数为 7 ，此时他前面的数为 6，最后一个 6 的索引为 5，此时我们返回 5 即可，如果目标数元素为 12，那么我们最后一个元素为 11，仍小于目标数，那么我们此时返回 8，即可。这个变种其实算是上面变种的相反情况，上面的会了，这个也完全可以搞定了，下面我们看一下代码吧。nums = {1,3,5,5,6,6,8,9,11} target = 7
