之前在数据结构搜索那章说过，折半（二分）一般适用于有序列表的查找，但是在写的时候需要注意算法的细节。我在leetcode上总共写了八道应用了二分算法的题目，从中总结一下写二分算法需要注意什么样的细节
一般二分查找
leetcode，第704题，binary search，
这道题就是最简单的二分查找算法，我当时的解法也是二分法，
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int middle = (end + start) / 2;
if(target > nums[middle]) {
start = middle + 1;
}else if(target < nums[middle]) {
end = middle - 1;
}else if(target == nums[middle]){
return middle;
}
}
return -1;
}
对于二分算法的写法，这是其中一种，还有其他写法，一共有三种模板写法
这上面的三种写法中，第三种是使用最多的，因为很多时候mid最好还是不要跳过，还需要继续使用。第一种写法写法更加简洁，不过适用于没有重复元素或者不需要寻找第一个、最后一个位置。我们可以发现模板写法和我们的写法有一点不同，这点就是mid的求法，模板中mid=left + (right - left) / 2，在我们的写法中middle = (end + start) / 2，我们的写法更容易出现问题，如果end和start这个时候都非常的大，超出了int的范围(-2147483648, 2147483647)，那么值就会变成0，但是模板中mid = left + (right - left) / 2就不会出现这样的问题。
leetcode，第278题，First Bad Version，
这道题也是查找位置，不过比较特殊，第一个版本错了，那么后面就会一直错，这个对错就是它的顺序，判断条件就是它对还是错。
public int firstBadVersion(int n) {
if(n == 1) return n;
int start = 1;
int end = n;
int bad_version = 1;
while(start <= end){
// 那种写法不对，middle = (start + end) / 2,
// 这种写法在小数据量下没关系，但是数据量大，就是相加错误
int middle = start + (end - start) / 2;
if(isBadVersion(middle)){
bad_version = middle;
end = middle - 1;
}else{
start = middle + 1;
}
}
return bad_version;
}
当然对于二分查找，也可以使用回溯法来实现它。
// 使用回溯法
public int firstBadVersion(int n) {
return helper(1,n);
}
public int helper(int start, int end) {
if(start >= end) return start;
int middle = start + (end - start) / 2;
// 这里和上面不同。这里并没有记录下来，并且middle可能就是的
if(isBadVersion(middle)) return helper(start, middle);
else return helper(middle + 1, end);
}
注意查找位置
这种题目一般都是因为查找的元素比较特殊，比如插入的位置，并且因为循环判定条件<=的原因，要格外注意位置在哪里。
leetcode，第35题，Search Insert Position，
这道题是一个插入题，其中应该注意的是返回值该是什么，下面的代码使用的是start来作为返回值，如果使用middle作为返回值，在数组也有相同元素的情况下没什么问题，一旦数组中没有这个元素，那么插入的位置就会小一格，而start是正好在位置上。
// 二分查找位置
public int searchInsert(int[] nums, int target) {
if(nums.length == 0) return 0;
int start = 0;
int end = nums.length - 1;
while(start <= end) {
int middle = (start + end) / 2;
if(target == nums[middle]) {
return middle;
}else if(target > nums[middle]) {
start = middle + 1;
}else if(target < nums[middle]) {
end = middle - 1;
}
}
// 要注意返回的位置，因为它可能会比插入位置的值要小
return start;
}
leetcode，第74题，Search a 2D Matrix,
这道题我是用的是俩次二分查找，因为它在行列上是有顺序的，我们可以先在行上二分，看目标数在哪一行中，找出特定行，但是要注意这个数在这个行中哪个位置。下面的代码用的是end来表示，这里如果用start，因为判断条件是<=，那么end最终会多出一格，因为执行了end++。
// 这里是用了俩次二分查找
// 也可以将二维数组并成一维数组
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0) return false;
int start = 0,end = matrix.length - 1;
int matrix_line = 0;
while(start <= end) {
int middle = (start + end) / 2;
if(target == matrix[middle][0]) {
return true;
}else if(target > matrix[middle][0]) {
start = middle + 1;
}else if(target < matrix[middle][0]) {
end = middle - 1;
}
}
// 注意查找的位置。这里不是插入，不应该用start
matrix_line = Math.max(end, 0);
start = 0;
end = matrix[matrix_line].length - 1;
while(start <= end) {
int middle = (start + end) / 2;
if(target == matrix[matrix_line][middle]) {
return true;
}else if(target > matrix[matrix_line][middle]) {
start = middle + 1;
}else if(target < matrix[matrix_line][middle]) {
end = middle - 1;
}
}
return false;
}
半有序
这种题目都是将数组旋转为前提，数组的全部元素并不是有序的，但是以某个元素为分界，俩边都是有序，当然也可以完全有序。
leetcode，第153题，Find Minimum in Rotated Sorted Array
，
上面就是以0为界限，前面有序，后面也有序。开始的时候，我的想法以第一个元素为标杆，这里就是4，然后二分，这里就是7与4进行比较，如果middle大于标杆元素，那么说明还在一个序列中，start = middle+1，直到找到了另一个有序，但是这种方法在面对序列中的元素都有序的时候就出错了，比如[1,2,3,4,5,6]，那么它肯定找不到了，因为都比标杆元素大。
之后想法是先找分界线，那么以最后一个元素为标杆比较好，因为如果一个序列中，那么最后元素都会比前面的大，如果中间元素middle大于最后元素end，说明俩者不在一个序列中，这个时候就可以将start往后移动，如果小于，就说明在一个序列中，可以将end往前移动。最后不确定start和end谁最小的最好方法就是比较一下。这里的判定条件已经发生了改变，变成了starrt + 1 < end，这是因为下面的不用再+1和-1，直接用了middle，如果还是以前的start <= end，整个程序就会没有发生变化，一直循环处理下去。
// 使用二分的思想，不至于全部遍历一下
// 速度很快
public int findMin(int[] nums) {
if(nums.length == 1) return nums[0];
int start = 0;
int end = nums.length - 1;
int target = nums[end];
while(start + 1 < end) {
int middle = start + (end - start)/2;
if(nums[middle] > target) {
start = middle;
}else if(nums[middle] < target){
end = middle;
target = nums[end];
}
}
return Math.min(nums[start], nums[end]);
leetcode，第154题，Find Minimum in Rotated Sorted Array II，
这道题最大的不同就是有了重复元素，但是其实解法都是一样的，只不过需要将重复元素进行判定消去，如果周边有相同的元素，那么就是移动一格。
// 大概的思路与之前的一样，重复元素，就简单的办法就是直接去除重复元素
// 但是时间太久，速度太慢，但是其他的思想都差不多。
public int findMin(int[] nums) {
if(nums.length == 1) return nums[0];
int start = 0;
int end = nums.length - 1;
int target = nums[end];
while(start + 1 < end) {
while(start < end && nums[end] == nums[end - 1]) {
end--;
}
while(start < end && nums[start] == nums[start + 1]) {
start++;
}
int middle = start + (end - start)/2;
if(nums[middle] > target) {
start = middle;
}else if(nums[middle] < target){
end = middle;
target = nums[end];
}
}
return Math.min(nums[start], nums[end]);
}
leetcode，第33题，Search in Rotated Sorted Array
这道题与上面俩道题差不多，只不过上面都是查找最值，这道题是查找相应的元素，一开始想法是双指针法，前后俩个序列，然后依次进行比较，因为这俩个序列也是有序，因而知道结束条件是什么。但是这种写法速度非常的慢。
// 将之变成俩个序列，分别使用顺序查找,速度有点慢
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int one_point = 0;
int two_point = nums.length - 1;
boolean is_one_search = true, is_two_search = true;
while(one_point < nums.length && two_point >= 0 && (is_one_search || is_two_search)) {
if(target == nums[one_point]) {
return one_point;
}else if(target > nums[one_point]) {
one_point++;
}else if(target < nums[one_point]) {
is_one_search = false;
}
if(target == nums[two_point]) {
return two_point;
}else if(target < nums[two_point]) {
two_point--;
}else if(target > nums[two_point]) {
is_two_search = false;
}
}
return -1;
}
之后看了别人的想法，发现二分也是可以解决这道题，不过二分需要判断四种情况：
- middle元素大于start元素，说明前面元素都是有序的。
- start < target < middle，那么该元素就在前面的序列中，这时end = middle，来缩小范围。
- 如果不在， 就得缩小到后面序列中，start = middle。
- middle元素小于end元素，说明后面元素都是有序的。
- middle < target < end，那么说明元素在后面的序列中，这时需要start = middle，来缩小范围。
- 如果不在，就得缩小到前面序列中，end = middle.
// 使用二分法，分四种情况进行讨论，速度可以，内存消耗大
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int start = 0;
int end = nums.length - 1;
// 这种start = middle写法中，判断条件不能是start < end，这样会导致它不变
while(start + 1 < end) {
int middle = start + (end - start)/2;
if(target == nums[middle]) return middle;
if(nums[start] < nums[middle]) {
if(target <= nums[middle] && target >= nums[start]) {
end = middle;
}else {
start = middle;
}
}else if(nums[end] > nums[middle]){
if(target >= nums[middle] && target <= nums[end]) {
start = middle;
}else {
end = middle;
}
}
}
// 这样判断最好，分清楚
if(nums[start] == target) return start;
if(nums[end] == target) return end;
return -1;
}
leetcode，第81题，Search in Rotated Sorted Array II
这道题和上面一样，只不过这道题多了重复元素，和之前一样的思路，先去除重复元素，再使用二分法来进行判断。
public boolean search(int[] nums, int target) {
if(nums.length == 0) return false;
int start = 0;
int end = nums.length - 1;
// 这种start = middle写法中，判断条件不能是start < end，这样会导致它不变
while(start + 1 < end) {
if(start < end && nums[start] == nums[start + 1]) start++;
if(start < end && nums[end] == nums[end - 1]) end--;
int middle = start + (end - start)/2;
if(target == nums[middle]) return true;
if(nums[start] < nums[middle]) {
if(target <= nums[middle] && target >= nums[start]) {
end = middle;
}else {
start = middle;
}
// 一定要加上这句话。不能直接写else,不然对于{3，1，1}这种无法判断
}else if(nums[end] > nums[middle]){
if(target >= nums[middle] && target <= nums[end]) {
start = middle;
}else {
end = middle;
}
}
}
if(nums[start] == target || nums[end] == target) return true;
return false;
}
总结
二分法(折半)思路较为简单，并且可以用在元素有序的情形下，但是二分法需要注意细节，停止条件，查找位置，判定条件，还有中间位置的计算。如果可以的话，先演示一下，要特别注意那些特殊情况下的写法。