二分法有「整数二分」和「实数二分」两种情况。实数二分的代码好写不易出错；整数二分的代码因为要考虑整除的问题，代码容易出错。
二分法的效率极高。比如在有序的n个数中找某个数，只需要二分log2n 次，也就是说它的时间复杂度是 O(log2n) 的。例如有 n = 10^7个数，只需要24 次就能找到答案。
总结一下，二分法把一个长度为 n 的有序序列上 O(n) 的查找时间，优化到了O(log2n)。注意，这个序列的数字一定要是「有序」的，二分才有意义。在乱序的一堆数字上搞二分，没有任何用处。所以这个数字序列如果是乱序的，应该先排序再二分。
只搜索一个数的话二分法不如直接暴力搜索，但是搜m个数。那么排序再二分就是 O(nlogn+mlogn)，而你的暴力法是 O(mn)的，显然就快多了。
几种常见的二分代码单调递增序列中找 x 或者 x 的后继
「在单调递增序列中找 x 或者 x 的后继」，即在单调递增数列a[] 中查找某个数 x，如果数列中没有 x，则找比它大的下一个数。左闭右开的编码，即[0,n)
int bin_search(int *a, int n, int x){ //a[0]～a[n-1]是单调递增的
int left = 0, right = n; //注意：不是 n-1，此时是左闭右开的[0,n)
while (left < right) {
int mid = left + (right-left)/2; //int mid = (left + right) >> 1;
if (a[mid] >= x) right = mid;
else left = mid + 1;
} //终止于left = right
return left; //特殊情况：a[n-1] < x时，返回n
}
当 a[mid] >= x 时，说明 x 在 mid 的左边，新的搜索区间是左半部分，left 不变，更新 right = mid。当 a[mid] < x 时，说明 x 在 mid 的右边，新的搜索区间是右半部分，right 不变，更新 left = mid + 1。代码执行完毕后，left = right，两者相等，即答案所处的位置。代码很高效，每次把搜索的范围缩小一半，总次数是 log(n)。 在单调递增序列中查找 x 或者 x 的前驱
「在单调递增序列中找 x 或者 x 的前驱」
int bin_search2(int *a, int n, int x){ //a[0]～a[n-1]是单调递增的
int left = 0, right = n;
while (left < right) {
int mid = left + (right-left + 1)/2 ;
if (a[mid] <= x) left = mid;
else right = mid - 1;
} //终止于left = right
return left;
}
当 a[mid] <= x 时，说明 x 在 mid 的右边，新的搜索区间是右半部分，所以 right 不变，更新 left = mid；当 a[mid] > x 时，说明 x 在mid 的左边，新的搜索区间是左半部分，所以 left 不变，更新 right = mid – 1。同样可以分析出，当 a[mid] > x 时，不能写成 right = mid，会导致 while() 的死循环。 第一题 分巧克力
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入：
2 10
6 5
5 6
样例输出：
2
import java.util.Scanner;
public class Main {
private static int max = 100000;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
int[] H = new int[max];
int[] W = new int[max];
for (int i = 0; i < N; i++) {
H[i] = scanner.nextInt();
W[i] = scanner.nextInt();
}
int left = 0, right = max;
while (left < right) {
int mid = left + (right - left + 1) / 2;
int temp = 0;
for (int i = 0; i < N; i++) {
temp = temp + (H[i] / mid) * (W[i] / mid);
}
if (temp >= K) {
left = mid;
} else {
right = mid - 1;
}
}
System.out.println(left);
}
}
第二题 跳石头 题目背景
一年一度的“跳石头”比赛又要开始了!
题目描述
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入输出格式 输入格式：
第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1且 N≥M≥0
接下来 N 行，每行一个整数，第 i行的整数 Di(0 一个整数，即最短跳跃距离的最大值。 25 5 2 4 真恶心 什么鬼物题 题目描述： 资源限制 欢迎分享，转载请注明来源：内存溢出
输入输出样例
输入样例#1：
输出样例#1：
2
11
14
17
21
import java.util.Scanner;
public class Main {
public static boolean check(int num, int[] stone, int N, int M, int mid) {
int count = 0;
int temp = 0;//当前石头位置
for (int i = 0; i < N; i++) {
if (stone[i] - temp < mid) {
count++;
} else {
temp = stone[i];
}
}
if (count > M) {
return false;
} else {
return true;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int L = scanner.nextInt();
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] stones = new int[50000];
for (int i = 0; i < N; i++) {
stones[i] = scanner.nextInt();
}
int left = 0, right = L;
int mid = left + (right - left) / 2;
while (left < right) {
mid = left + (right - left) / 2;
if (check(mid, stones, N, M, mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(left);
}
}
时间限制：1.0s 内存限制：256.0MB
问题描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求三个实根。。
输入格式
四个实数：a，b，c，d
输出格式
由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位
样例输入
1 -5 -4 20
样例输出
-2.00 2.00 5.00
数据规模和约定
|a|，|b|，|c|，|d|<=10
import java.util.Scanner;
public class Main {
public static double figure(double a, double b, double c, double d, double num) {
return a*num*num*num+b*num*num+c*num+d;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
double a = scanner.nextDouble();
double b = scanner.nextDouble();
double c = scanner.nextDouble();
double d = scanner.nextDouble();
for (int i = -100; i <= 100; i++) {
double left = i, right = i + 1;
double num1 = figure(a, b, c, d, left);
double num2 = figure(a, b, c, d, right);
if(num1==0){
System.out.println(String.format("%.2f",left));
}
if (num1 * num2 < 0) {
for (int j = 0; j < 100; j++) {
double mid = (left + right) / 2;
if (figure(a, b, c, d, left) * figure(a, b, c, d, right) <= 0) {
left = mid;
} else {
right = mid;
}
}
System.out.println(String.format("%.2f",right));
}
}
}
}
微信扫一扫
支付宝扫一扫
评论列表（0条）