本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
二分法
今天来学习下二分法的相关知识点。 二分查找算法是高效且应用广泛的一种查找算法，它要求待查找的对象（数组或者列表）是有序的。下面先看下二分法的经典实现，在一个有序的数组中，查找目标值
target，若存在，返回该值的位置；若不存在，则返回
-1。
迭代版
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 被查找的数字要么不存在，要么必然在nums[left...right]中
while(left = right) {
int mid = left + (right - left) / 2;
if(nums[mid] target) {
left = mid + 1;
} else if(nums[mid] target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
观察以上实现发现，使用了有序索引数组，来标识被查找的目标值可能存在的子数组的大小范围
nums[left...right]。在查找时，先将被查找的目标值和子数组的中间值比较。
递归版
根据以上迭代版的时候，很容易实现等价的递归版本。
public int searchInsert(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
public int binarySearch(int[] nums, int target, int left, int right) {
// 中止条件
if(right left) {
return -1;
}
int mid = left + (right - left) / 2;
if(nums[mid] target) {
// 继续查找右子数组
return binarySearch(nums, target, mid + 1, right);
} else if(nums[mid] target) {
// 继续查找左子数组
return binarySearch(nums, target, left, mid - 1);
} else {
// 查到目标值
return mid;
}
}
时间复杂度
二分查找算法，在
n个元素的有序数组中，最多需要
logn + 1次比较（无论是否成功），故时间复杂度为
O(log(n))。 二分法的高效来自能够快速通过索引取得任何子数组的中间元素。
空间复杂度迭代版：
O(1)
递归版：
O(log(n))，调用栈
相关题目
35. 搜索插入位置
本题来自 LeetCode：35. 搜索插入位置[1]
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
题目分析
典型的二分法，只需要在未找到目标值时，返回其本来的位置，即返回小于目标值
target元素的个数。
题目解答
迭代版
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 被查找的数字要么不存在，要么必然在nums[left...right]中
while(left = right) {
int mid = left + (right - left) / 2;
if(nums[mid] target) {
left = mid + 1;
} else if(nums[mid] target) {
right = mid - 1;
} else {
return mid;
}
}
// 这里left表示数组中小于目标值的元素数量
return left;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
递归版
class Solution {
public int searchInsert(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
public int binarySearch(int[] nums, int target, int left, int right) {
if(right left) {
return left;
}
int mid = left + (right - left) / 2;
if(nums[mid] target) {
return binarySearch(nums, target, mid + 1, right);
} else if(nums[mid] target) {
return binarySearch(nums, target, left, mid - 1);
} else {
return mid;
}
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(log(n))
278. 第一个错误的版本
本题来自 LeetCode：278. 第一个错误的版本[2]
题目描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有
n个版本
[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用
bool isBadVersion(version)接口来判断版本号
version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) - false
调用 isBadVersion(5) - true
调用 isBadVersion(4) - true
所以，4 是第一个错误的版本。
题目分析
二分法，剪枝的时候，中间值只有两种可能：
true和
false。
题目解答
class Solution {
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while(left = right) {
//int mid = (left + right) 1; 不可行，有符号右移，如果left和right比较大，会溢出
// int mid = (left + right) 1; 可行
// int mid = left + ((right - left) 1); 可行
int mid = left + (right - left) / 2;
if(isBadVersion(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
374. 猜数字大小
本题来自 LeetCode：374. 猜数字大小[3]
题目描述
我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口
guess(int num)，它会返回
3个可能的结果
（-1，1 或 0）：
-1 : 我的数字比较小
1 : 我的数字比较大
0 : 恭喜！你猜对了！
示例 :
输入: n = 10, pick = 6
输出: 6
题目分析
二分法，剪枝的时候，中间值有三种可能：
lower、
higher、
equal。
题目解答
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public static final int LOWER = -1;
public static final int HIGHER = 1;
public int guessNumber(int n) {
int left = 1;
int right = n;
while(left = right) {
int mid = left + ((right - left) 1);
if(guess(mid) == LOWER) {
right = mid - 1;
} else if(guess(mid) == HIGHER) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
153. 寻找旋转排序数组中的最小值
本题来自 LeetCode：153. 寻找旋转排序数组中的最小值[4]
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为
[4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
题目分析
由于数组进行了旋转，故不是一个完全有序的数组。但是隐含的一个细节就是，如果子数组
[left...right]有序，那么最小值一定出现在左半部分。 因此本题如果
要进行二分法剪枝的话，就必须确定好哪部分子数组是有序的。
题目解答
解法一
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int min = Integer.MAX_VALUE;
while(left = right) {
int mid = left + (right - left) / 2;
min = Math.min(min, nums[mid]);
if(nums[left] nums[right]) {
// 剪右子数组
right = mid - 1;
} else if(nums[left] nums[right]) {
// 左子数组，只剪掉left位置
left ++;
} else {
return min;
}
}
return min;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
解法一在最差的情况下，复杂度为
O(n)，因为只剪了右半部分数组。比如
[2, 3, .., n, 1]。 进一步优化，可以从
nums[left] nums[right]这个条件入手。
上面提到，
要进行二分法剪枝的话，就必须确定好哪部分子数组是有序的。那么需要通过区间
[left...mid...right]来判断左子区间
[left...mid]和右左子区间
[mid...right]哪部分是有序的。这个就很好判断了，因为我们知道
nums[left]、
nums[mid]、
nums[right]这三者的值；
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int min = Integer.MAX_VALUE;
while(left = right) {
int mid = left + (right - left) / 2;
min = Math.min(min, nums[mid]);
// [left...right]有序，最小值一定出现在左子数组
if(nums[left] nums[right]) {
// 剪右子数组
right = mid - 1;
// [left...right]不是有序的，最小值可能出现在左边，也可能出现在右边
} else if(nums[left] nums[right]) {
// 表示[mid...right]是有序的，那最小值一定出现在左子数组
if(nums[mid] = nums[right]) {
right = mid - 1;
// 表示[left...mid]是有序的，那最小值一定出现在右子数组
} else if(nums[mid] nums[right]) {
left = mid + 1;
}
} else {
return min;
}
}
return min;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
33. 搜索旋转排序数组
本题来自 LeetCode：33. 搜索旋转排序数组[5]
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为
[4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是
O(log n)级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
题目分析
二分法，和上题类似，剪枝的时候，需要小心。
题目解答
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left = right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
return mid;
}
// [left...right]有序，target必然在区间[left...right]中
if(nums[left] nums[right]) {
if(nums[mid] target) {
left = mid + 1;
} else {
right = mid - 1;
}
} else if(nums[left] nums[right]) {
// 表示[mid...right]是有序的，需要判断target是否位于[mid...right]内
if(nums[mid] = nums[right]) {
// target在区间[mid...right]中
if(nums[mid] target && target = nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
// 表示[left...mid]是有序的，需要判断target是否位于[left...mid]内
} else if(nums[mid] nums[right]) {
// target在区间[left...mid]中
if(nums[left] = target && target nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
} else {
return -1;
}
}
return -1;
}
}
复杂度分析：
时间复杂度：
O(log(n))
空间复杂度：
O(1)
参考资料
搜索插入位置: https://leetcode-cn.com/problems/search-insert-position/
第一个错误的版本: https://leetcode-cn.com/problems/first-bad-version/
猜数字大小: https://leetcode-cn.com/problems/guess-number-higher-or-lower
寻找旋转排序数组中的最小值: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
搜索旋转排序数组: https://leetcode-cn.com/problems/search-in-rotated-sorted-array
原文始发于微信公众号（xiaogan的技术博客）：
