二分

二分查找法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间，但它有一个前提，就是必须在有序数据中进行查找。

二分查找很好写，却很难写对，据统计只有10%的程序员可以写出没有bug的的二分查找代码。出错原因主要集中在判定条件和边界值的选择上，很容易就会导致越界或者死循环的情况，本人在看了Acwing视频后有了一定的体会，写了下面的文章

整数二分

二分的本质：把一个区间一分为二，一半满足某个性质，一半不满足某个性质，然后将区间进行划分

eg：上图划分成两个边界，此时要寻找红绿颜色的边界

第一种情况：寻找红颜色的边界点

mid=（l+r+1）/2//注意这个+1，不然会出现死循环，例如l与r只差1，且check(mid)==true会出现死循环​if(check(mid)){//check(mid)作用是判断mid是否满足红颜色的性质//边界点在[mid,r]之间，更新方式，l=mid​}else{//边界点在[l,mid-1]之间，更新方式，r = mid-1}

第二种情况：寻找绿颜色的边界

mid = (l+r)/2​if(check(mid)){//check(mid)作用是判断mid是否满足绿颜色的性质，如果满足，那么绿颜色的边界点一定在[l,mid]之间//边界点在[l,mid]之间，更新方式为r=mid}else{//边界点在[mid+1,r]之间，更新方式为l = mid+1}

给定一个二分问题如何考虑：先写一个check函数，根据check(mid)判断如何更新

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n ,m;n = scanner.nextInt();m = scanner.nextInt();int[] arr = new int[n];for (int i = 0; i < arr.length; i++) {arr[i] = scanner.nextInt();}while (m--!=0){int x = scanner.nextInt();int l = 0, r = arr.length-1;while (l<r){int mid = (l+r)>>1;if(arr[mid]>=x)r = mid ;//找出第一个比x大的arr[mid],//那么arr[mid]后面的数都会比x大,这时只需要将r更新成mid即可将区间进行划分了else l = mid+1;}if(arr[l]!=x) System.out.println("-1 -1");else {System.out.print(l+" ");int l1 = 0,r1 = arr.length-1;while (l1<r1){int mid = (l1+r1+1)>>1;if(arr[mid]<=x) l1 =mid;//找出最后一个比x小的arr[mid],//那么arr[mid]前面的数字都是比x小的，此时就可以把区间更新成l1 = mid进行划分else r1 = mid-1;}System.out.println(l1);}}scanner.close();}}

浮点数二分

相较于整数二分而言，浮点数二分就显得更为简单了，浮点数二分没有边界问题需要考虑

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);double i = scanner.nextDouble();double l = 0,r = i;double eps = 1e-8;while (r-l>eps){//当r与l之间相差10的-8以上时，就可以把r或l当成答案了double mid = (r+l)/2;if(mid*mid*mid>=i) r = mid;//这里是>=的原因是找到第一个数满足mid的立方比i更大，//mid后面的数的立方都会比i大，这时只需要取mid的左边的数据就行,即为r = midelse l = mid;}System.out.println(l);scanner.close();}}