二分查找算法可以说是很基本的一个算法思想，如果写成题目一般是这样的形式：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
来源：力扣704
别看这样一道小题，我在面试的那么多次中还碰到过三次，这样的题目当然是信手拈来，直接默写下来的，最多两分钟搞定。
还记得高三物理老师给我说过的一句话：“自信过头了，就会阴沟里翻船。”那时候我对物理的学习兴趣浓厚，当然有兴趣的前提是，物理最后一道大题总能作对，并且对力学的各种分析乐此不疲。物理老师对我说这句话的时候，拿着我的考试卷子做分析，答题除了计算错误扣了几分外，几乎全对，而选择题却红刷刷，左一刀，右一刀，错了一片。
求根号x
几年前，去找实习工作，我又翻了船，一个人不会踏入同一条河流，但可以在同一条河流中翻两次船。当时，面试官写了一道二分查找的题目出来，我一看题目心里就一股不屑，这题还拿出来考，直接拿过来，三笔两笔默写出来，默写出来的代码，长这个样子：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
复制代码然后，面试官又写下了一道题目：
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
来源：力扣-69
并且要求不能用库函数，这题该怎么做，还不能用库函数，难道用加减乘除吗？这道题目并不难，但当时我一下就懵了，就好像是我正踩着高跷走在冰面上，突然冰面碎了，我一下掉进了软绵绵的深水中，脑子一片空白，没办法思考了。
我后来回想，面试官还是挺不错的，让我去树上摘苹果，先给了我一把梯子，我却告诉面试官：“我用不着梯子，您没看见我踩着高跷呢，够得着。”
结果高跷不如梯子管用，我摔得够呛，好在面试官还是把梯子帮我竖了起来，拉我起来，在面试官的提示下，我勉强做出来了。而当时使用的解法正是二分查找的套路。
思路是这样滴！
假设根号x的整数部分为a，那么a满足
，a的下限是1，上限可以粗略的认为是x，如果要找到下限和上限之间最接近答案的那个数字，就可以使用二分法逐次逼近了。代码如下。
class Solution {
public int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = x;
while(true) {
int mid = (right - left) / 2 + left;
if (mid > x / mid) {
right = mid - 1;
} else {
if ((mid + 1) > x / (mid + 1)) {
return mid;
}
left = mid + 1;
}
}
}
}
复制代码需要注意的是，这里的代码的第8行和第11行不能用乘法代替，因为比较大的数可能导致数据溢出变成负数，从而造成死循环。
从这次面试之后，我再也不敢轻视二分查找了，这个小小的算法，有大大的用处。有很多题目都可以用到二分查找的思想。我也明白了一个道理，刷题不在多，关键是要融会贯通，学会题目的思想，能举一反三，就拿二分查找的例子来说，如果碰到类似的题目，能否想到用二分查找来解决，如何解决，如果刷算法题目，有了这种能力，就不怕新题目了，因为题目再新，原理还是那些原理。下面举几个使用二分查找思想的例子。
二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
来源：力扣-230
二叉搜索树的中序遍历是有序的，这个题目可以使用中序遍历的方式来做。不过，这里主要看一下如何使用二分查找的思想来做这道题目。
树的结构很容易让人想到从中间劈开，一分为二。而二叉搜索树的根元素又是树的中间值，左小，右大。
对于图中的二叉树（a）来说，根节点15的左子树的个数为4，如果要找第5小的，那就刚好是根节点，如果要找第3小的，就要到左子树（b）中去继续寻找，如果要找第6小的，就要去右子树（c）中寻找，去右子树（c）中寻找第几小的呢，这个数要减去左子树的个数+1，因为右子树的节点都是大于根节点和左子树的。代码清单如下：
class Solution {
public int kthSmallest(TreeNode root, int k) {
int n = count(root.left);
if (k <= n) {
return kthSmallest(root.left, k);
} else if (k > n + 1) {
return kthSmallest(root.right, k - n - 1);
}
return root.val;
}
private int count(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + count(root.left) + count(root.right);
}
}
复制代码寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2
示例 2:
输入: [3,1,3,4,2] 输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
来源：力扣-287
这个题目有几种解法，这里专注一点，只讨论二分查找的方法。要说清楚这个方法，我们先来看个例子。
对于数组[1,2,6,4,4,5,3]，重复的元素是4，如果以4为分隔把数组分成两部分，一部分是(1,2,3)，一部分是(6,4,4,5)。
定义函数f(x)表示在数组中小于等于x的元素的个数，那么有
f(1) = 1;
f(2) = 2;
f(3) = 3;
f(4) = 5;
f(5) = 6;
f(6) = 7;
复制代码也就是说，如果数组中的重复元素是d，数组中只有一个重复的数字，但它可能不止重复出现一次，有以下关系：
数组的范围已经给定了，使用二分法和公式(1)和(2)，可以逐步缩小重复元素可能出现的范围。对于数组[1,2,6,4,4,5,3]，下面使用二分法推演找到重复元素的过程。
- 第一步：left = 1， right = 6，mid = 3，数组中小于等于mid的个数为3，符合公式(1),说明重复元素在[mid+1, rihgt]这个区间；
- 第二步：left = 4，right = 6，mid = 5，数组中小于等于mid的个数为6，符合公式（2），说明重复元素在[left, mid]这个区间；
- 第三步：left = 4，right = 5，mid = 4，数组中小于等于mid的个数为5，符合公式（2），说明重复元素在[left, mid]这个区间；
- 第四步：由于left = right，结束，答案为4。
如果把上述过程翻译成代码，为：
class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1;
while (left < right) {
int mid = (right - left) / 2 + left;
int cnt = 0;
for (int v : nums) {
if (v <= mid) {
cnt++;
}
}
if (cnt <= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
复制代码使用二分查找思想的题目还有一些，比如：
近期评论