二分

• 整数二分:

  bool check(int x) {/* ... */} // 检查x是否满足某种性质
  
  
  // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  //用于寻找最左出现的数
  static int bsearch_1(int l, int r,int x)
  {
      while (l < r)
      {
          int mid = l + r >> 1;
          if (check(mid)) r = mid;//即使已满足条件，也继续向左推进
          else l = mid + 1;//产生跳出条件
      }
      return l;
  }
  // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  //用于寻找最右出现的数
  static int bsearch_2(int l, int r,int x)
  {
      while (l < r)
      {
          int mid = l + r + 1 >> 1;//+1，防止死循环
          if (check(mid)) l = mid;//即使已满足条件，也继续向右推进
          else r = mid - 1;//产生跳出条件
      }
      return l;
  }

  例题：

  • acwing1227:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    	private static int[][] arr = new int[100005][2];
    	private static int N;
    	private static int K;
    
    	public static void main(String[] args) throws IOException {
            //读取输入
    		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    		String[] str = bf.readLine().split(" ");
    		N = Integer.parseInt(str[0]);
    		K = Integer.parseInt(str[1]);
    		for (int i = 0; i < N; i++) {
    			str = bf.readLine().split(" ");
    			arr[i][0] = Integer.parseInt(str[0]);
    			arr[i][1] = Integer.parseInt(str[1]);
    		}
            //在1到100000这个区间中使用二分，寻找最终答案
            int l = 1, r = 100000;
    		while (l < r) {
    			int mid = l + r + 1 >> 1;
    			if (check(mid))//满足条件则向右偏移
    				l = mid;
    			else
    				r = mid - 1;//产生跳出条件
    		}
    		System.out.println(l);
    
    	}
        
        //判断是否满足条件
    	private static boolean check(int mid) {
    		int num = 0;
    		for (int i = 0; i < N; i++) {
    			num += (arr[i][0] / mid) * (arr[i][1] / mid);
    		}
    		if (num >= K)
    			return true;
    		else
    			return false;
    	}
    }

• 浮点数二分：

  bool check(double x) {/* ... */} // 检查x是否满足某种性质
  
  double bsearch_3(double l, double r)
  {
      const double eps = 1e-6;   // eps 表示精度，一般取所求精度小2
      while (r - l > eps)
      {
          double mid = (l + r) / 2;
          if (check(mid)) r = mid;
          else l = mid;
      }
      return l;//写r和l都可以
  }

  例题：

  • 洛谷p1024:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    	private static double a;
    	private static double b;
    	private static double c;
    	private static double d;
    
    	public static void main(String[] args) throws IOException {
            //读取输入
    		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    		String[] str = bf.readLine().split(" ");
    		a = Double.parseDouble(str[0]);
    		b = Double.parseDouble(str[1]);
    		c = Double.parseDouble(str[2]);
    		d = Double.parseDouble(str[3]);
            
            //以1为长度单位，遍历每一个区间
    		for (double i = -100; i <= 100; i++) {
    			double l = i, r = i + 1;
    			if (ans(l) == 0) {
    				System.out.printf("%.2f ", l);
    				continue;
    			} else if (i <= 99 & ans(l) * ans(r) < 0) {
                    //在长度为1的区间中使用二分法查找实根
    				while (r - l > 1e-4) {
    					double mid = (r + l) / 2;
                        //值在x轴同一侧
    					if (ans(l) * ans(mid) > 0)
    						l = mid;
    					else  //值在x轴异侧
    						r = mid;
    				}
    				System.out.printf("%.2f ", l);
    			}
    
    		}
    
    	}
        
        //返回表达式的值
    	static double ans(double x) {
    		return a * x * x * x + b * x * x + c * x + d;
    	}
    
    }