二分查找思想：
二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
基础二分查找：
/* * 如果查找到了，就返回所在的下标，如果找不到，就返回-1*/ public static int binarySerach(int []array,int key){ int left=0,right=array.length-1; //这个等于号必不可少 while (left<=right){ int mid=left+(right-left)/2; //防止溢出 if (array[mid]==key) return mid; else { if (key<array[mid]){ //则在左边 right=mid-1; }else { //则在右边 left=mid+1; } } } return -1; //如果走到这边，一定是找不到了。。。 }
二分变种
1.求第一个大于等于key的元素
分析：假设有数组1 3 4 6 8 12 ，这个时候a[mid]是6，而需要找的key是5,所以a[mid]>=key，在原来的基础二分的时候是：right=mid-1;但是要注意，我们需要找的是第一个大于等于key的值，所以这个a[mid]很有可能是我们需要找的数据，因而不能减去，所以这个时候是：right=mid；而如果a[mid]<key的话，原来基础二分是：left=mid+1；这里也是一样的。
//找到第一个大于等于key的元素的下标 public static int findFirstLarger(int []array,int key){ int left=0,right=array.length-1; while (left<=right){ int mid=left+(right-left)/2; //防止溢出 if (array[mid]<key){ left=mid+1; }else{ right=mid; /*这里有个bug，如果left=0 right=1 那么mid=0，且往右边查找、 * 那么left=mid+1=1,那么就 left==right * 那么就会陷入死循环*/ if (left==right)break; } } return left; //return right都一样 }
2.找到第一个小于key的值的元素
分析：其实很简单，可以变成查找第一个大于等于key的值的元素然后-1即可。
代码就和上面的一样。只是结果自己-1
3.找到第一个大于key的值的元素
分析：还是很简单的弄到第一种方式的变更，一开始对key加1就好了。然后就变成找到第一个大于等于key的值的元素。
题目：对于一个从左往右递增，从上往下也递增的二维数组，输入某个key，判断该key是否存在于二维数组中。
思路：首先对二维数组的列进行二分查找，找到第一个大于或等于key的值的位置，然后再对那一行进行二分查找即可。时间复杂度：log2n+log2m
public static boolean findNum(int [][]array,int key){ int times=array.length; //对行进行二分，找到第一个大于或等于的key的值 int low=0;int high=times-1; while (low<=high){ int mid=(low+high)/2; if (array[mid][0]>=key){ high=mid-1; } else { low=mid+1; } } if (high<0) return false; //那么这个时候的low就是所在的 if (low<times&&array[low][0]==key){ return true; }else { //对其上一行进行二分查找 int left=0,right=array[low-1].length-1; while (left<=right){ int mid=(left+right)/2; if (array[low-1][mid]==key){ return true; }else { if (array[low-1][mid]>key){ right=mid-1; }else { left=mid+1; } } } return false; } }
总结：
发现了一篇很好的关于二分的博客：https://www.cnblogs.com/luoxn28/p/5767571.html