I. 定义
二分法是一种通常用在排序数据集或者不完全排序的数据集中查寻元素的一种算法。其清晰的逻辑，简单的时间复杂度（O(logn)）使得其非常流行。
II. 二分法的思路
二分法的思路非常简单，我们用一个简单的问题来解释一下。
假设我们的问题是在一个[1, 2, 3, 4, ..., 99, 100]的数组中找到70这个数的index。解决这个问题我们最开始想到的思路就是遍历整个数组，把70和index 1, index 2, …index 100 的数比较，最终找到其位置。但是我们知道，这样的算法时间复杂度为O(n), 在实际操作中是非常没有效率的。那么二分法又是怎么来解决这个问题的呢？
二分法顾名思义，就是将数据集首先从中间切开，分成左右两个子数据集。然后判断出查询的数据集在哪个子数据集中，接着对这个子数据集做这样的递归操作，直到找到要查找的对象或者数据集不可再分为止。
在数组nums = [1, 2, 3, 4, ..., 99, 100]的数组中找到target = 70这个数的index的问题中，二分法的过程是这样的：
- 找到中位数也就是index为49的数——50，接着判断target是否等于它。如果等于直接返回中位数的index，如果不等于就继续。
- 将数组拆分为
[1, 2 ,..., 49, 50]和[51, 52, ... 99, 100]两个数组。如果target大于中位数,那么对右侧的子数组再次执行一遍二分法，反之则对左侧子数组执行。 - 一直循环二分法下去直到找到target或者子数组无法再分为止。
III. 四重境界
二分法的使用分为四重境界。随着境界的提升，难度会加大。让我们依次来分析它们。注意，一定要使二分法不会陷入死循环。
第一境界——在排序数组上进行二分
在排序数组上使用二分法是最自然的想法，过程就如同在上述二分法思路的那样进行。模板代码如下：
Java
public int binarySearch(int[] nums, int start, int end, int target) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
其步骤是如下：
1.将一个数组nums,以及它的左右两端的index还有要找的数target传入到函数中：
public int binarySearch(int[] nums, int start, int end, int target) {
2.开始while循环，为了避免出现死循环，我们设置当start + 1 < end时循环继续：
while (start + 1 < end) {
3.计算出中位数的index, 为了避免溢出，在java中要用如下方式进行计算：
int mid = start + (end - start) / 2;
4.如果中位数和target相等，返回中位数的index：
if (nums[mid] == target) {
return mid;
}
5.如果中位数小于target,对右侧数组进行新的二分法,反之则左侧：
else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
6.结束循环后，由于我们还没有判断最终的start和end位置上的数是否等于target，所以我们要重新手段判断一次。如果还是没有找到target，则返回-1：
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
第二境界——在不完全排序数据集(OOXX)上二分
有的时候，数组并不是完全排序的，但是却有一定的规律，当数组中的元素可以分为O和X两种的时候，可能我们依然可以使用二分法来解决问题。
经典习题
Find Minimum in Rotated Sorted Array(Lintcode 159)
Description
Suppose a sorted array in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You can assume no duplicate exists in the array.
这道题目是要我们在一个Rotatd Sorted数组中找到最小值，且数组中没有重复的数。这道题是一道典型的在OOXX数组上使用二分查找的题目。比如在nums = [3, 4, 5, 0, 1, 2]中，前三项就是X,后三项就是O,而我们要找的数就是第一个O。这道题目我们可以通过画图的方式分析出，我们要找的第一个O是一个小于nums[0]，而且小于它的前一项的数。另外所有的O都是小于nums[0]的,这样我们就很容易判断出我们二分后的中位数是在O区间还是X区间了。
Note: 当然也有一种例外，那就是最小值为
nums[0](数组在length * n次旋转后后保持不变） 的情况，我们需要首先测试它
Java代码
public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return -1;
}
if (nums[0] < nums[nums.length - 1]) {
return nums[0];
}
return binarySearch(nums, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < nums[start]) {
end = mid;
}else {
start = mid;
}
}
return nums[start] < nums[end] ? nums[start] : nums[end];
}
}
代码解析
1.异常检测：
if (nums == null || nums.length == 0) {
return -1;
}
2.判断nums[0]是否为最小数，如果是，返回nums[0]:
if (nums[0] < nums[nums.length - 1]) {
return nums[0];
}
3.调用binarySearch函数查找最小数：
return binarySearch(nums, 0, nums.length - 1);
4.使用binarySearch模板，修改一些部分：当中位数小于start的时候，证明我们在O区间，最小值在左侧数组，所以对左侧子数组再进行二分。反之中位数则在X区间，那么我们要去到包含所有O区间的右侧子数组：
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] < nums[start]) { //mid在O区间，最小值在左侧
end = mid;
}else { //mid在X区间，最小值在右侧
start = mid;
}
}
5.对start和end进行手动判断：
return nums[start] < nums[end] ? nums[start] : nums[end];
第三境界——在未排序的数据集上二分
当数组既不是排序数组，也不符合XXOO特性的时候，如果我们可以找到一种每次二分数组后判断出必定有解的那一半，我们依旧可以使用二分法继续对必定有解的那一半进行二分直到找到解或不可再分为止。
经典习题
Find Peak Element(Lintcode 75)
Description
English
There is an integer array which has the following features:
- The numbers in adjacent positions are different.
- A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peak if:
A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.
- It’s guaranteed the array has at least one peak.
- The array may contain multiple peeks, find any of them.
- The array has at least 3 numbers in it.
Chinese
你给出一个整数数组(size为n)，其具有以下特点：
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定*P*是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。
- 数组保证至少存在一个峰
- 如果数组存在多个峰，返回其中任意一个就行
- 数组至少包含 3 个数
这道题给定的数组并不是排序的，但是我们可以找到一定的规律。数组的开始端是上升的，结束端是下降的，而山峰必定是在上升和下降之间。那么如果我们二分出来的中位数在下降的位置，在它的左侧必然有峰；当中位数在上升的位置，那么右侧必然有峰。找到这样的规律后，我们就可以在每次二分时判断左右两侧子数组那一侧必定有解，然后对这一侧继续二分直到找到解为止。
Java代码
public class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return -1;
}
int start = 1, end = A.length - 2;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < A[mid - 1]) {
end = mid;
} else if (A[mid] < A[mid + 1]) {
start = mid;
} else {
return mid;
}
}
if (A[start] < A[end]) {
return end;
} else {
return start;
}
}
}
代码解析
1.异常检测：
if (A == null || A.length == 0) {
return -1;
}
2.设置二分法最初的范围，数组左右两端必然不是峰，为了避免溢出，范围如下：
int start = 1, end = A.length - 2;
3.开始二分法，如果中位数在下降段，对左侧数组进行二分；反之对右侧数组进行二分：
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < A[mid - 1]) { //中位数在上升段
end = mid;
} else if (A[mid] < A[mid + 1]) { //中位数在下降段
start = mid;
} else { //中位数是峰
return mid;
}
}
4.对start和end再做一次判断,因为题目给定的数组必定有峰，那么我们比较它们之间的大小即可：
if (A[start] < A[end]) {
return end;
} else {
return start;
}
第四境界——自己找到答案区间并二分
有时题目并没有给定我们一个数组，我们依旧可以使用二分法。当我们不知道解，但是可以确定解的范围的时候，我们可以用二分法对答案的范围进行缩小直到找到解为止。
经典习题
Wood Cut(Lintcode 183)
Description
English
Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.
You couldn’t cut wood into float length.
If you couldn’t get >= k pieces, return
0.
Chinese
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回
0即可。
虽然这道题目并没有给我们一个数组并在上面找到解，但是我们可以锁定解的范围，并用二分法找到解。我们知道切出来的木头的长度至少为单位1，最多不能超过总原木的长度/要且出来的数量。这样我们就锁定了解的范围，接下来我们只需要找到最大满足条件的解即可。
Python代码
class Solution:
"""
@param L: Given n pieces of wood with length L[i]
@param k: An integer
@return: The maximum length of the small pieces
"""
def woodCut(self, L, k):
# write your code here
if not L or sum(L) < k:
return 0
maxLen = sum(L) // k
return self.binarySearch(L, 1, maxLen, k)
def binarySearch(self, L, start, end, k):
while start + 1 < end:
mid = (start + end) // 2
if self.isWoodEnough(L, mid, k):
start = mid
else:
end = mid
if self.isWoodEnough(L, end, k):
return end
else:
return start
def isWoodEnough(self, L, woodLength, k):
count = 0
for i in L:
count += (i // woodLength)
if count >= k:
return True
else:
return False
代码解析
1.异常检测：
if not L or sum(L) < k:
return 0
2.锁定解的范围，并调用binarySearch找到解：
maxLen = sum(L) // k
return self.binarySearch(L, 1, maxLen, k)
3.使用binarySearch找解，我们用isWoodEnough函数来判断中位数的解是否满足解的条件。如果不满足，我们则在左侧子数组中找满足条件的解；如果满足，我们就在右侧数组继续找满足条件的更大的解。
def binarySearch(self, L, start, end, k):
while start + 1 < end:
mid = (start + end) // 2
if self.isWoodEnough(L, mid, k): #解满足条件
start = mid #在右侧子数组找更大的解
else: #在左侧子数组中找解
end = mid
#对start和end进行判断
if self.isWoodEnough(L, end, k):
return end
else:
return start
4.isWoodEnough函数计算出当木头长度为woodLength时，切出来的木头的数量是否能够 大于等于k：
def isWoodEnough(self, L, woodLength, k):
count = 0
for i in L:
count += (i // woodLength)
if count >= k:
return True
else:
return False
IV. 总结
二分法是一种非常实用且流行的查找算法。我们可以使用它在排序数组、XXOO数组上求解。如果我们可以在二分后判断出解在那一半子数组中也可以使用二分法。当我们给可以锁定解的范围的时候，依旧可以用二分法在范围中找到解。
Share this post
Twitter
Google+
Facebook
Reddit
LinkedIn
StumbleUpon
Pinterest
Email