二分法那点事～

发布: 分类: 评论次数： 阅读次数： 本文字数： 1.8k

今天呢，因为这几天做了一些关于二分法的题，就想着写篇文章记录一下对二分法的几种常用方法。实际上的原因是我怕自己过几天就忘了，所以写下防忘（其实我已经在onenote上做好笔记了，只是为了随时随地能看到，加深印象而已）

二分法的模版

相信很多人都曾用过这个方法，因为它的时间复杂度是很低的，在一般情况下它的复杂度能够达到log(n)，因此很适合在有序的列表里进行元素的查找

那么，二分法的基本模版又是怎样的呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

注意：代码片段里的省略号处都是需要自己注意填写的地方

至于mid的计算方式：left + (right - left) / 2是因为防止left + right溢出

查找指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(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; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

首先，注意下，这里的right=nums.length - 1,表示这里的循环中的每一次搜索区间都是左闭右闭的（因为right的值是可以达到的），也正因为是左闭右闭的，所以while的循环条件里需要添加等号

其次，由于是左闭右闭，每次循环中，对left与right的赋值都必须是闭合的，也就是说不能包括mid（因为mid已经判断过了）

查找指定元素的最左边界

题目可能有点拗口，简单点来说，就是找到第一个大于等于指定元素的下标（为什么会大于呢，因为如果没有这个元素，就会找第一个大于这个元素的下标值，比如[2,3,4,6,7]，target=5，那么找到的值就是下标3）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int left_Bound(int[] nums, int target){
    if(nums.length==0){
        return -1;
    }
    int left = 0;
    int right = nums.length;
    int middle;
    while(left<right){
        middle = left + (right - left) / 2;
        if(nums[middle]>=target){
            right = middle;
        }else if(nums[middle]<target){
            left = middle + 1;
        }
    }
  	return left;
    //if(left==nums.length) return -1;
    //return (nums[left]==target)?left:-1;
}

注意：最后两行是指如果没有这个元素，就返回-1，有的话就返回left

解释：

  1. 平时如果是搜索最左边界或者最右边界，就使用左闭右开（right = nums.length），因为这样返回值更容易理解，为什么呢，因为左闭右开，表示while循环条件是不带等号，那么退出的时候就一定是left=right的时候退出循环，试想两种极端情况：left一直不动，right一直动，最后返回值就是left=0；right一直不动，left一直动，最后返回值就是left = right = nums.length。所以返回值就在[0,nums.length]
  2. 由于是搜索最左边界，那么当middle的值等于target的时候，不直接返回，而是继续将right=middle(或者right = middle - 1，左闭右闭)，继续向左逼近
  3. 最后，返回值方面就看当middle等于target的时候，自己写的right赋值是什么了，比如说，right=middle，这就表示返回值是left(或者right，两者相等)，如果是right = middle - 1（这是将区间设置为左闭右闭的情况，不常用）,那么返回值就是lef t+ 1(right + 1)
  4. 如果要求没有该元素，返回-1，就判断我们返回的值left，如果等于nums.length，表示target比所有值都大，导致left不断向右移动；如果等于0，则表示target小于等于第一个值，需要判断第一个值是否等于target再进行返回

查找指定元素的最右边界

题目的实际意思，简单点来说，就是找到第一个大于指定元素的下标值，举个例说：[1,2,3,3,3,4,5]，target=3

，那么返回值就是下标值5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int right_bound(int[] nums, int target){
    if(nums.length==0){
        return -1;
    }
    int left = 0;
    int right = nums.length;
    int middle;
    while(left<right){
        middle = left + (right - left) / 2;
        if(nums[middle]<=target){
            left = middle + 1;
        }else if(nums[middle]>target){
            right = middle;
        }
    }
  	return left-1;
    //if(left == 0) return -1;
    //return (nums[left-1]==target)?left-1:-1;
}

解释：

  1. 首先，这里也是使用的左闭右开（right=nums.length），因此循环条件不带等号，right=middle(right的赋值也需要是开的，middle已经判断过，[left,middle) )，left=middle + 1(left的赋值需要是闭的，[middle+1,right) )
  2. 当middle的值等于target的时候，不急着返回，而是将left继续向右逼近（因为找的是最右边界），left = middle + 1
  3. 返回值方面，看middle等于target情况下的赋值：left = middle + 1,所以最后返回的是left - 1(middle = left - 1)
  4. 最后，如果需要元素不在则返回-1，需要根据left-1的值来判断，如果left=0，那么left-1就越界，直接返回-1，如果left是nums.length，则需要判断nums.length-1的位置的值与target是否相等

结束

以上就是我个人对二分法目前最常用的三种形式的理解，肯定是很粗浅的啦，望大佬勿喷～