二分算法只需背两种模版

二分算法只需背两种模版 整数二分

有单调性，必然可以二分。如果没有单调性，也可能可以二分，二分的本质并不是单调性。

模版

//区间[l, r]被划分成[l, mid]和[mid + 1, r]使用
int bsearch_1(int l, int r){
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid; // check()判断mid是否满足性质。
		else l = mid + 1;
	}
	return l;
}

//区间[l, r]被划分成[l, mid - 1]和[mid, r]使用
int bsearch_2(int l, int r){
	while(l < r){
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

先写一个check函数，如果更新方式是 l = mid + 1，则把int mid = (l + r) / 2改成int mid = (l + r + 1) / 2。
核心就是看更新区间是l = mid还是r = mid，如果是l = mid，就需要把int mid 改成 mid = (l + r + 1) / 2。这个+1也是为了避免循环过程中发生死循环，避免搜索区间不变。
ACwing整数的范围

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = in.nextInt();
        }
        while(q-- != 0){
            int target = in.nextInt();
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(target <= nums[mid]) r = mid;
                else l = mid + 1;
            }//这么写的话，最后输出的是nums数组中，满足target <= nums[mid]的最极限的那个数，也就是大于等于target的数的最小的索引
            if(nums[l] != target){
                System.out.println("-1 -1");
            }else{
                System.out.print(l + " ");
                l = 0;
                r = n - 1;
                while(l < r){
                    int mid = l + r + 1 >> 1;
                    if(target >= nums[mid]) l = mid;
                    else r = mid - 1;
                }//这么写的话，最后输出的是nums数组中，满足target >= nums[mid]的最极限的那个数，也就是小于等于target的数的最大的索引
                System.out.println(l);
            }

        }
    }
}

上面这个我是这么写的，但看ACM模式，他们常常把N，也就是数据的长度，作为全局变量先定义出来。

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int n, m;
    static int[] q = new int[N];
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < n; i ++) q[i] = sc.nextInt();
        while(m -- !=  0){
            int x;
            x = sc.nextInt();
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(q[mid] >= x) r = mid;
                else l = mid + 1;
            }
            if(q[l] != x) System.out.println("-1 -1");
            else{
                System.out.print(l + " ");
                int l1 = 0, r1 = n - 1;
                while(l1 < r1){
                    int mid = l1 + r1 + 1 >> 1;
                    if(q[mid] <= x) l1 = mid;
                    else r1 = mid - 1;
                }
                System.out.println(r1);
            }
        }

    }
}


作者：空_22
链接：https://www.acwing.com/solution/content/32357/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。