二分探索是什么？
二分搜索(binary search )又称折半搜索，是一种在有序数组中搜索特定元素的搜索算法。
两点检索需要什么条件？
必须是顺序存储结构；
必须按照关键字的大小顺序排列。
二分搜索原理
使用二分搜索算法在arrays数组中找到8个位置
int [ ] arrays=new int [ ] { 2，8，12，18，20，25，30，37，41，49，61 }；
规则阵列被分成三个部分，分别是中间值之前(中间值数目之前的数据组)、中间值和中间值之后)、中间值之后的数据组)； 比较要搜索的数字和中间值，如果相等，则结束搜索，如果小，则在中间值之前进行比较，如果大，则在中间值之后进行比较，并顺序递归，直到找到对应的值； 如果要搜索的数据结构为偶数，则中间值mid必须进行抽取处理。 上述arrays阵列的中央值为{25}，中央值之前为{2、8、12、18、20}，中央值之后为{30、37、41、49、61}。 二分搜索计算原理图如下。
二分搜索是两种常用的方式
非递归
publicclassbinarysearch { publicstaticvoidmain { string [ ] args }
integer [ ] array={ 5，2，10，8，7 }； 使用Arrays.sort对数组进行排序，默认情况下按升序排列。 要实现降序，请使用arrays.sort(array，Comparator )实现自定义排序
Arrays.sort(Array )；
系统. out.println (find (array，7 )；
} publicstaticbooleanfind (integer [ ] array，Integer param ) {int start=0； int end=array.length - 1； intmid； 使用wile(start=end )//位运算是为了防止start end溢出
mid=(开始) 1； if (array [ mid ]==param ({返回真；
(//start、end必须取当前mid值的高位或低位，注意不要发生死循环。 例如，start为3，end为4，mid=(startend )/2一直为3，发生死循环
if(Array[mid]
开始=mid 1；
}else{
end=mid - 1；
}
}返回假；
}
}
递归
publicclassbinarysearch { publicstaticintrank，int[] a
{返回链路(key，a，0，a.length-1 )；
}publicstaticintrank(intkey，int[] a，int lo，inthi ) ) ) ) ) ) ) ) ) )。
{if(Lohi ) /左边界下标大于带边界下标时，不满足条件，
返回- 1； intmid=lo(hi-lo )/2； if (密钥)
rank(key，a，lo，mid-1 )； 是elseif(keymid )
Rank(key，a，mid 1，hi )； 返回节点id；
}
}
时间的复杂性和空间的复杂性
时间复杂性：
最坏的情况是两种方式的时间复杂度相同。 o(log2n )；
根据情况o(1；
空间复杂性：
计算算法的空间复杂度是计算整个算法的辅助空间单元的数量，而不是计算实际占用的空间
非递归方式：辅助空间为常数级，因此空间复杂度为o(1)；
递归方式：递归的次数和深度都为log2 N，每次所需的辅助空间为常数级。 空间复杂度： o(log2n )。
二分搜索中位数(mid )计算二分搜索中位数计算有两种方法。
intmid=(lowhigh )/2；
int mid=low (高低)/2；
上述两种算法，第一种看起来很简洁。 第二个提取后，和第一个没有太大区别。 但是，实际上上述两种计算有区别，第一种方法是在极端情况下计算，(low high )有溢出的风险，进而可能会得到错误的mid结果，导致程序错误。 第二种算法确保计算出的mid值一定大于low、小于high，不存在溢出问题。 在第一种算法中，int mid=(high low ) 1，以防止溢出问题； 解决这个问题。
两点探索的优缺点：
优点：比较次数少，检索速度快，平均性能好。
缺点：必须有序，一定要
须是数组。引申
解决二分查找缺陷问题更好的方法是使用二叉查找树，最好自然是自平衡二叉查找树，既能高效的(O(n log n))构建有序元素集合，又能如同二分查找法一样快速(O(log n))的搜寻目标数。
问题
以上的二分查找解决不了如下几个问题：
变体一：查找第一个值等于给定值的元素
比如下面这样一个有序数组，其中，a[5]，a[6]，a[7] 的值都等于 8，是重复的数据。我们希望查找第一个等于 8 的数据，也就是下标是 5 的元素。
首先拿 8 与区间的中间值 a[4] 比较，8 比6 大，于是在下标 5 到 9 之间继续查找。下标 5 和 9 的中间位置是下标 7，a[7] 正好等于8，所以代码就返回了。尽管 a[7] 也等于 8，但它并不是我们想要找的第一个等于 8 的元素，因为第一个值等于 8的元素是数组下标为 5 的元素。
public classBinarySearch {public static voidmain(String[] args) {int[] array = { 5, 2, 10, 8, 7};//使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序
Arrays.sort(array);
System.out.println(find(array,10));
}public static int find(int[] a, intvalue) {int low = 0;int high = a.length - 1;//注意终止条件为low>high，因为low==high的这个元素有可能就是需要被查找的。
while (low <=high) {//这种写法主要为了防止(low+high)/2超过int的上限值
int mid = low + ((high - low) >> 1);//如果a[mid]>value，说明只能存在于[low~mid-1]
if (a[mid] >value) {
high= mid - 1;//同理若a[mid]
} else if (a[mid]
low= mid + 1;//这时候a[mid]==value，但是不一定是第一个等于value的
} else{//如果第一个元素等于value，很明显，那就返回第一个元素的地址。如果mid的前一个元素不等于value，直接返回，否则继续往前找
if ((mid == 0) || (a[mid - 1] !=value)) {returnmid;
}else{//否则low不变，high往前移动一位，继续寻找
high = mid - 1;
}
}
}return -1;
}
}
变体二：查找最后一个值等于给定值的元素
public classBinarySearch {public static voidmain(String[] args) {int[] array = { 5, 2, 10, 8, 7, 10};//使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序
Arrays.sort(array);
System.out.println(find(array,10));
}public static int find(int[] a, intvalue) {int low = 0;int high = a.length - 1;//注意终止条件为low>high，因为low==high的这个元素有可能就是需要被查找的。
while (low <=high) {//这种写法主要为了防止(low+high)/2超过int的上限值
int mid = low + ((high - low) >> 1);//如果a[mid]>value，说明只能存在于[low~mid-1]
if (a[mid] >value) {
high= mid - 1;//同理若a[mid]
} else if (a[mid]
low= mid + 1;//这时候a[mid]==value，但是不一定是第一个等于value的
} else{//如果最后一个元素等于value，很明显，那就返回最后一个元素的地址。如果mid的后一个元素不等于value，直接返回，否则继续往后找
if ((mid == a.length - 1) || (a[mid + 1] !=value)) {returnmid;
}else{//否则high不变，low往前移动一位，继续寻找
low = mid + 1;
}
}
}return -1;
}
}
变体三：查找第一个大于等于给定值的元素
在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。
public classBinarySearch {public static voidmain(String[] args) {int[] array = { 5, 2, 10, 8, 7, 10};//使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序
Arrays.sort(array);
System.out.println(find(array,6));
}public static int find(int[] a, intvalue) {int low = 0;int high = a.length - 1;while (low <=high) {int mid = low + ((high - low) >> 1);if (a[mid] >=value) {//第一个元素就比目标值大，那结果就是第一个元素。或者mid的前一个元素小于value，那此时mid就是那个元素
if (mid == 0 || a[mid - 1]
}else{//否则将high往前移动一位，继续寻找
high = mid - 1;
}
}else{//如果a[mid]
low = mid + 1;
}
}return -1;
}
}
变体四：查找最后一个小于等于给定值的元素
查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是6。
public classBinarySearch {public static voidmain(String[] args) {int[] array = { 5, 2, 10, 8, 7, 10};//使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序
Arrays.sort(array);
System.out.println(find(array,6));
}public static int find(int[] a, intvalue) {int low = 0;int high = a.length - 1;while (low <=high) {int mid = low + ((high - low) >> 1);if (a[mid] >value) {//将high往前移动一位，继续寻找
high = mid - 1;
}else{//如果mid是最后一个元素，肯定就是他了。或者mid后面那个元素大于value，此时返回mid
if ((mid == a.length - 1) || (a[mid + 1] >value)) {returnmid;
}else{//否则low继续后移
low = mid + 1;
}
}
}return -1;
}
}
注：其实二分查找的重点就是在一轮没有查找到结果后，low以及high的值如何改变的问题