Java|实现二分法查找

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章

前言

不知道大家玩过这么一个游戏没—猜数字大小。先在心里想一个100以内的数字,然后参与者来猜数字,每次只提示大了或者小了,直到参与者猜中心中所想的数为止。

怎么来快速猜出来呢?利用二分法查找就可以快速实现。接下来给大家讲解二分法查找的思想,以及如何用java代码实现。

二分法查找的思想

二分法查找又称为折半查找,二分法查找的基本思想是把数组中的元素从小到大有序地存放进数组中,首先将给定值与数组中间位置的值作比较,如果相等,则匹配成功。否则,若比较值小了,则在数组的前半部分继续二分法查找;若比较值大了,则在数组后半部分进行二分法查找。如此循环往复,直到比较值与中间值匹配,完成查找。

流程图:

Java|实现二分法查找

Java代码实现:

public class test {
public static void main(String[]  args) {
//        定义数组
int[] arr  ={81,51,88,15,59,20,1,50,66,77,4};
//        对数组进行升序排序
Arrays.sort(arr);
//        打印数组
System.out.println(Arrays.toString(arr));
//        打印查找结果
System.out.println(binarySearch(arr,59));
}
public static int  binarySearch(int[]arr,int value){
int low = 0;
int high = arr.length-1;
//        循环直到不能再分
while (low<=high){
int mid = (low+high)/2;
if (value == arr[mid]){
//                返回匹配值的下标
return mid;
}
if (value < arr[mid]){
high = mid-1;
}
if (value > arr[mid]){
low = mid+1;
}

}
//        如果没有查找到值,则返回404
return 404;
}
}

效果展示

打印了数组,并输出了查找值的索引

温馨提示

在这里,有一个非常值得注意的点,二分法查找的前提是排好序的数组。所以我在上面代码中使用了sort()方法,对初始数组进行了排序。

END

主  编   |   张祯悦

责  编   |   王    宇

where2go 团队

   

微信号:算法与编程之美          

Java|实现二分法查找

长按识别二维码关注我们!

温馨提示: 点击页面右下角 “写留言”发表评论,期待您的参与!期待您的转发!

原文 

http://mp.weixin.qq.com/s?__biz=MzI5MTQ5NDY1MA==&mid=2247489978&idx=1&sn=7157827d92e104348192c4b3fc0e2f08

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java|实现二分法查找

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址