189 8069 5689
这篇文章主要介绍了Java如何实现二分查找，具有一定借鉴价值，需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让小编带着大家一起了解一下。
创新互联主营图们网站建设的网络公司,主营网站建设方案,app软件开发公司,图们h5小程序开发搭建,图们网站营销推广欢迎图们等地区企业咨询
二分查找特别好理解，就类似于快排和归并当中用到的分治的思想，每次取中间数与目标数相比较，然后确定是大了还是小了，区间折半。
就比如：
小红选中了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如何实现二分查找内容对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，遇到问题就找创新互联，详细的解决方法等着你来学习!