找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法与人生(三)

admin 2019-4-12 05:31 90人围观 C++相关

每当有这种阴晴不定的天气的时候,整个人好像漂浮在水里的蜉蝣,承受着海水的击打,拖着疲惫的身体努力地向前游着,而灵魂却在自由地游荡着。有那么一刹那,好像我看见了平行空间里的自己,孤独地游弋在花花世界之中,脸上挂着虚伪的笑容,像极了小丑。

来首音乐舒缓下情绪吧,慰藉我们的心灵。



今天,我想与大家分享的算法是查找中很简易也常见的考点——二分法。从字面意思来看,二分法就是将原本一份的东西分成两份,在查找里面,就是将原来的数组分成两个数组再查找。



类对称风景(图片来自网络,侵删)

注意到,分出来的两个数组不一定需要等长,所以我们的分界点也不一定是最中间的那个点(如下图所示)。



二分查找需要的输入数组是有序的,即已经按照一定的顺序排列好的,因此经常需要先排序然后再查找。

比如说我们希望查找一个数组lst = [2,4,5,7,9,11,12,14]里的某一元素num = 4的位置,我们假定中间元素的位置是len(lst)/2-1。如下图所示:



由于数组是已排好序的,可知中间点左侧[2,4,5]都是比中间点元素值小的元素,右侧[9,11,12,14]都是比中间点值大的元素。我们首先比较给定元素num = 4与中间点值middle = 7的大小,比中间点值大则在右侧寻找,比中间点值小则在左侧寻找。由上例可知比中间点值小,则在左侧寻找,找到左侧中间点len(lst.left)/2-1。如下图所示:



比较给定元素num = 4与中间点值middle = 4的大小,发现正好匹配,找到中间点元素的位置,查找结束。

整个过程的代码如下附(python):
    def Binary_Search(lst, num):    lens = len(lst)-1    firstid= 0    lastid = lens    while firstid <= lastid:        middle = int(firstid + (lastid - firstid) / 2)        if num < lst[middle]:            lastid = middle - 1        elif num > lst[middle]:            firstid = middle + 1        else:         return middle    return lastid

    二分法是个从思路到代码量都很简单的算法。

    我觉得整个二分法的精髓在于如何去找到这个中间点,当然是对于有模棱两可的中间点的时候。对于第二幅图来说,如果我们需要找的值正好是中间点2,我们选取的中间点是1,那么我们为了找到这个值,需要花费3倍的功夫;如果选取的中间点是2,直接就能找到。我想告诉大家的是:选择往往真的很重要,甚至在某些情况下超过了努力。

    人生在世,如白驹过隙,但选择却犹如海浪般连绵不绝。比如起床第一眼是去看手机呢还是穿衣服呢?考试时是选择A还是选择C呢?工作是去微软亚研院还是去IBM呢?对于我这种轻微选择困难症的人来说,只有通过深思熟虑和权衡利弊后才能做出选择,但往往会失去很多东西~

    怎么去做选择?在我看来,第一直觉未必对,深思熟虑未必优,关键是不后悔。在摩托和奔驰间我选择摩托,在别人看来你的选择很幼稚。但是只要你不后悔,没准奔驰是有安全隐患,可能开上路就出了严重的交通事故,而摩托是辆哈雷也说不定呢。

    选择关注我的公众号,不会让你后悔!

    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:月下旧梦集,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......

    
    关于进行手机实名认证的紧急通知!
    按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了