二分查找迥殊好明白，就类似于快排和合并当中用到的分治的头脑，每次取中间数与目的数相比较，然后确定是大了照样小了，区间折半。
就比方：
小红选中了1-100中的某个数字（这个数字是56），要小明来猜，发生以下对话：
小明第一次猜想：68
小红：大了
小明第二次猜想：35
小红：小了
小明第三次猜想：58
小红：大了
小明第四次猜想：49
小红：小了
小明第五次猜想：54
小红：小了
小明第六次猜想：56
小红：bingo！！！
我们能够看到在上面的对话中，小明每次猜想都能够减少区间，直到回覆准确
二分查找就是如许的，比方我们如今有数组8，11，19，23，27，33，45，55，67，98，用二分查找以下图：
每次都能够减少一半的区间，我们能够看到区间变化以下：
当区间大小无穷靠近1的时刻k = log2n，所以时候庞杂度为O(logn)。
是否是迥殊好明白，下面是我用Java完成的简朴的二分查找（备注：是最简朴的完成，二分查找的变体很庞杂还没控制）
package com.structure.search;
/**
* 二分查找法
*
* @author zhangxingrui
* @create 2019-02-15 21:29
**/
public class BinarySearch {
public static void main(String[] args) {
int[] nums = new int[]{4, 6, 9, 19, 30, 40, 500, 3450, 50004, 4334343};
System.out.println(binarySearch(nums, 0, nums.length - 1, 30));
System.out.println(binarySearch(nums, 50004));
}
/**
* @Author: xingrui
* @Description: 二分查找法（针对有序数组且不存在反复元素-递归体式格局完成）
* @Date: 21:37 2019/2/15
*/
private static int binarySearch(int[] nums, int p, int r, int k){
if(p > r)
return -1;
int mid = (p + r) / 2;
if(nums[mid] == k)
return mid;
if(k > nums[mid])
return binarySearch(nums, mid + 1, r, k);
else
return binarySearch(nums, p, mid - 1, k);
}
/**
* @Author: xingrui
* @Description: 二分查找法（针对有序数组且不存在反复元素-轮回完成）
* @Date: 21:37 2019/2/15
*/
private static int binarySearch(int[] nums, int k){
int p = 0;
int r = nums.length - 1;
while (p <= r){
int mid = (p + r) / 2;
if(nums[mid] == k)
return mid;
if(k > nums[p])
p = mid + 1;
else
r = mid - 1;
}
return -1;
}
}
代码很简朴，个中须要注重的就是边界条件p<=r。
从代码也能够看出，简朴完成有很大的局限性，只能适用于有序的不存在反复数据的数组。
而且二分查找不太合适小规模的数据查询（由于小规模的数据查询没有必要），这个好明白；同时呢，也不合适太大的数据的查询，这又是为啥子呢？
就是由于上面提到的：二分查找合适底层运用数组的数据，然则数组呢又是一段一连的内存空间，当数据很大的时刻假如要用二分查找，那末数据的底层完成就
只能用数组，如许就不太好了。假定我的数据有一个G，那末我就要请求1个G的一连内存空间，妈哟，怕吃饱球了。
以上就是Java完成二分查找的基础要领（附代码）的细致内容，更多请关注ki4网别的相干文章！
