二分 | 东川

二分

二分的核心思想，就是根据check函数取划分

整数二分

整数二分，稍微麻烦点，有两套模板

模板

// 情况1
public static int bsearch(int[] arr, int l, int r){
    while(l < r){
        int mid = l + r >> 1;
        if(check[mid]){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    return l;
}

//情况二
public static int bsearch(int[] arr, int l, int r){
    while(l < r){
        int mid = l + r + 1 >> 1; //很关键
        if(check[mid]){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    return l;
}

题目

AcWing的两道题

P789 数的范围整数二分
P790 数的三次方根浮点二分

P789

描述

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

分析：找两遍，找一个最左边的，找一个最右边的

解答

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = sc.nextInt();
		int[] arr = new int[n];
		
		for(int i=0;i<n;i++)
		{
			arr[i] = sc.nextInt();
		}
		while(count-- != 0)
		{
			int target = sc.nextInt();
			
			//1. 找起始位置
			//二分来做
			int l = 0;
			int r = n-1;
			while(l < r)
			{
				int mid = l + r >> 1;
                //你要找到起始位置，题目说了升序，我们就找最小的
				if(arr[mid]>=target) //满足吗？
					r = mid;
				else
					l = mid + 1;
			}
			
			if(arr[l]!=target)
			{
				System.out.println("-1 -1");
			}
			else
			{
				System.out.print(l + " ");
				//2. 找最右边的那个
				l = 0;
				r = n-1;
				
				while(l < r)
				{
					int mid = l + r + 1 >> 1;
					if(arr[mid]<=target)
						l = mid;
					else
						r = mid -1;
				}
				System.out.println(l );
			}
			
		}
		
	}
}

此题是升序的，其实二分的前提就是有序

P790

描述

给定一个浮点数n，求它的三次方根

解答

// 此题其实就是浮点二分

/*
 * 请用二分来做
 * 
 */

import java.util.*;
import java.io.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		double n = Double.parseDouble(br.readLine());
		
		double l = 0;
		double r = Math.abs(n);
		
		while(r-l >= 1e-8)
		{
			double mid = (l + r)/2; //这里因为是浮点二分，所以很方便
			if(mid*mid*mid >= Math.abs(n)) //abs可以很快，忽略负数情况
				r = mid;
			else
				l = mid;
		}
		
		if(n >= 0)
		{
			System.out.println(String.format("%.6f", l));
		}
		else
		{
			System.out.println("-"+String.format("%.6f", l));
		}		
	}
}