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

     实事求是的说二分搜索是我学习算法的时候学的最好,理解的最透彻,能够当时就写出代码的的算法。事到如今,就如我可以分分钟写出hello world一样,我可以分分钟写出一个二分搜索算法,曾经几何时,这曾经是我在大学时面对一众连hello world都不会写的同学的装高手利器,我曾以为我可以带着这份荣耀感一直到我找到下一份荣耀感,但是终有一天残酷的现实总能无声的击碎无力的意淫。

     先不考虑二分搜索的各种本体形式,先从最简单的非递归版本看起吧,以下是粗略易错在我写程序的前几个月一直认为没有错并且我觉得在实际应用上一定能用的版本:

//四个参数,数组,开始点,终止点,查找值
//当然这个函数可以再包装一下成为只传数组,数组大小和查找值
int BinarySearch(const int list[],int start,int end,int key)
{    while(start<=end)
    {
        int mid=(start+end)/2;
        if(list[mid]<key) start=mid;
        else if(list[mid]>key) end=mid;
        else return mid;

    }
    return -1;
}

     上面的代码粗一看绝对很难看出问题在哪,这也是我曾经一直以为这样是正确的原因,但是直到有一天当时一个大牛用了一组测试数据的时候立马打破了我所有的幻想。传统上,这里都要说,先不要朝下看喔,先自己想想能不能找出错误,这么多年来,每当我在书上看到这句话我都会果断往下看。

     让我们从最小的冲击开始,不妨试试这样的测试数据:

const int index=10;
int testArr[index];
for(int i=0;i<index;i++) testArr[i]=i;
cout<<BinarySearch(testArr,0,index-1,index-1)<<endl;

     你会发现善意的小黑框并没有任何数据,在你等了十秒之后幡然领悟貌似是死循环的时候,你才会猛然惊醒查看是不是代码的哪个环节已经操蛋了,通过采用最吊丝的输出中间下标的方法查看到了在某一段时间后,mid的值不变了,这才领悟到应该把start=mid改成start=mid+1,同时我也猛然间领悟到为什么在二分搜索的递归本体中的一些细节了。这是我还在非常初级阶段时犯得错误,但是就是这个错误让我意识到任何一个程序都是那么容易做的完美的,特别是你作为一个写代码的不会知道调用代码的会是怎样的一个格式,代码得具有大爱,得具有包容性。

      冲击波略微升级,万一传入的数组是一个没有排过序的怎么办?什么?你说这不可能,二分搜索就是应该传入排序好的数组,先不说这世界上本来就没有什么是应该的,就说无论是有意挑战还是无意调用,这种情况都是极端常见的,所以说在这种情况下,什么二分搜索算法什么高效率瞬间成浮云,这和智能手机再怎么吊,也怕一盆水是一个道理,所以才有所谓三防技术的出现。那怎么避免这种情况呢?我见到的有两种,一个是在真正进行搜索之前无论传入的数组有没有排序,都进行一次的排序工作,第二种是用一个循环,遍历整个数组,如果发现未排序的立马输出错误,return该return的值。这两种虽然牺牲了效率,但是可以确保二分搜索不会被一盆水弄得完全不可以工作。

      接着,偶然的机会我又遇到了如下这个强大型冲击波,比如

struct StudentInfo
{
    int grade;//分数
    string name;//姓名
}SI; 

     对于这样一个含有这样结构的数组进行二分搜索,找到分数大于等于60分,也就是没有挂科的人的名字,这个问题很重要,我相信对于大多数人不会希望在某一个统计挂科的名册中发现自己是传说中的六十分但是因为自己的名字按某种默认的规则是排在前面的而被一个不完备的算法所漏统计吧?也许你还没有意识到我说的是什么问题,如果用不废话的版本,如果二分搜索的数组中有重复的数字,怎么处理这一情况,是返回第一个重复的数字还是返回最后一个,或者是随便返回一个。这个问题在上面那个应用背景下就很有意义了,更别说查询什么账户余额大于多少的程序里,毕竟,一旦扯上钱,任何细微的地方都是值得考虑的,如果某一个人因为默认排序而被漏掉,后果大多数情况下应该都比较难搞。

      所以,真心觉得任何一个小程序想写的完美都不简单,如果真的想要写的一个完美的程序,细节才是最重要的,使用怎样的技巧证明的是你有没有成为一个优秀程序员的潜质,而能不能考虑到大部分细节绝逼是你能不能成为一个工程师,一个真的开发人员的品质啊,所以,共勉啊,同志们!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

使用Block提高代码可读性

最近一直在思考并持续的扩充着自己的技术栈,比如每天坚持着学习前端知识,并且时常想着在移动端这条路上,自己的技术盲区。诚然,想要在一个领域达到一定的技术高度是挺困...

1083
来自专栏编舟记

我是怎样学习新编程语言的

学习新的编程语言的最终目的是解决实际问题。掌握编程语言的过程,在某种程度上近似学习一种新的工程实践。不仅解决问题固然可乐,学习的过程也同样充满了新鲜感,不过需要...

1223
来自专栏编程

器—术—道:程序设计教材建设经验谈

《计算机教育》2017年第11期 封面文章 引 言 程序设计的境界有3种:器—术—道。在程序设计能力培养方面,一般由“器”入门,通过熟悉“术”,最终达到“道”的...

2209
来自专栏编程

英语不好,能看懂编程吗?

学会编程不需要多高深的英语水平,想要学会编程,简单的英语水平足够了,现在的程序开发环境又很友好,基本上打开之后不需要怎么配置,直接写代码就行,程序语言无外乎顺序...

2220
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 七、项目:机器人

3356
来自专栏Pythonista

面向对象的软件开发

很多人在学完了python的class机制之后,遇到一个生产中的问题,还是会懵逼,这其实太正常了,因为任何程序的开发都是先设计后编程,python的class机...

1252
来自专栏逸鹏说道

重温数据结构系列随笔:数据结构的基本概念

现在项目已经踏上正轨,有不少时间可以用来学习,昨晚发现柜子里那本大学时候啃过无数遍的(数据结构 C语言版),那真的无限感叹啊,初恋女友啊,大学回忆啊都涌上心头。...

2944
来自专栏程序人生

抽象的能力

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

3467
来自专栏Alan's Lab

JS 变量提升

问到 JS 一些细节问题的时候发挥比较糟糕,有些是知道反应得太慢,有些是压根没接触过,还是积累的太少了。这篇的 JS 变量提升问题就是从没有接触过的,网上一搜一...

2672
来自专栏web前端教室

这几天在看JS的数据结构与算法

这几天在看数据结构与算法,js描述这书 ? 这书看着标题挺高大上的,但内容不难, 只要有JS的基本知识,都能看明白。 它里面不讲JS本身如何,而是把各种数据结...

2268

扫码关注云+社区

领取腾讯云代金券