重温二分查找算法(r4笔记第66天)

二分查找在学习算法的时候会涉及到,算是一个基本的分治思想,对于算法的实现大家也都是很熟悉的,但是这个时候真会犯眼高手低的毛病。不信你自己试试,看你能够在段时间内写出可运行的二分查找算法。 二分查找算法的思想非常易于理解,但是能够写出一个准确的二分查找程序绝非一个很简单的事情,从历史上来看,而非思想早在1946年就出现了,但是第一个完全正确的二分查找算法确实在1962年出现,计算机专家曾说过,90%以上的计算机专家不能再2个小时内写出完全正确的二分查找算法。我反正是应了这句话,不过我不是计算机专家。 我们来看一个比较标准的二分查找算法

package new_test;


public class BinarySearch {
int arr[];
public static void main(String args[]){
test();
}
public int binarySearch(int t,int[] arr){
int left=0;
int right=arr.length;
int middle;
while(left<=right){
middle=(left+right)/2;

if(t==arr[middle]){
return middle;
}
if(t>arr[middle]){
left=middle+1;
}
if(t<arr[middle]){
right=middle-1;
}
}
return -1;

}

public static void test(){
int[] arr=new int[]{1,2,5,7,8,10,11,15,19,20};
System.out.println(	new BinarySearch().binarySearch(8, arr));
}
}

运行结果是4,即arr[4]=8 其实这个算法还有一些值得思考的细节。比如求得两个数之和的平均数 如果直接写为middle=(left+right)/2就很可能出现数值溢出的情况。 可以使用下面的形式来避免,算法博大精深,细节决定成败。 middle=left+(right-left)/2;

原文发布于微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文发表时间:2015-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

NOIP普及组初赛题型分析

初赛的考察内容的一部分是计算机的基础知识,比如进制转换,工作原理,算法原理、历史事件名人等。这些对于大部分第一次参加noip的同学来说应该比较陌生,这样的知识只...

772
来自专栏大数据钻研

由浅入深的前端面试题 和矫情的“浪漫主义”诗句

好吧,我承认太标题党了,这篇文章是通过一道前端面试题引出的纯技术讨论。我先要矫情无比的从中外诗歌说起。 传统的佛学经典里,被世人熟知的有这样一句话:“一花一世界...

34610
来自专栏工科狗和生物喵

【计算机本科补全计划】CCF计算机职业资格认证 2017-03 试题初试

正文之前 我在之前的文章中提到过,我的老师要求我的CCF 考试考个280分来打个底,(没错,我就是那个横跨考研、工作、保研三大领域的男人)相当于是测试下我的能力...

9829
来自专栏take time, save time

[细节决定B度]之二分搜索也不易啊

     实事求是的说二分搜索是我学习算法的时候学的最好,理解的最透彻,能够当时就写出代码的的算法。事到如今,就如我可以分分钟写出hello world一样,我...

3086
来自专栏阿凯的Excel

乘积求和及符合某个条件的乘积求和

如何得到两个数组的乘积求和呢??案例如下: ? 已知每个地市的销售单价和销售数量,需要知道整个表的销售总金额,怎么做??? 普通青年做法: ? 小编客观公正...

4319
来自专栏程序人生

抽象的能力

人类的智商从低幼逐渐走向成熟的标志之一就是认识和运用数字的能力。当我们三四岁的时候,数数虽然能够熟练地对一百以内的数字随心所欲地倒背如流,但数字对孩童时代的我们...

3457
来自专栏我是攻城师

统计学里面的百分位数是什么意思

6035
来自专栏杨建荣的学习笔记

大整数乘法的算法分析(r12笔记第42天)

昨天看了下Paxos协议,比我想象的要复杂。每次都没能耐着性子看完。但是隐隐感觉就跟钓鱼一般(尽管我没用真实试过),如果有耐性,能坚持还是能够明白的。 ...

2735
来自专栏算法channel

动态规划中篇:爬楼梯

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

4099
来自专栏ThoughtWorks

像机器一样思考|TW洞见

今日洞见 文章作者、部分图片来自ThoughtWorks:仝键。 本文所有内容,包括文字、图片和音视频资料,版权均属ThoughtWorks公司所有,任何媒体、...

3747

扫码关注云+社区

领取腾讯云代金券