由二分查找说起

二分查找一种时间复杂度为O(log n)的经典查找方法。大体步骤是先进行排序,然后定义两个指针:头指针和尾指针。每次比较头指针和尾指针对应区间内最中间的数值和查询数值的大小,即将搜查区间一分为二,然后这样排除一半的区间,从而提升查找效率。
python代码如下:

def bin_search(array,token):
    low = 0
    high=len(array)-1
    while low<=high:
        mid = (low+high)//2
        if array[mid]==token:
            return mid
        elif array[mid]<token:
            low = mid+1
        else: high = mid -1
    return -1

二分查找的算法本身非常简单,但是它的整体思路还是非常值得借鉴的,它的双指针结构和分治思路在很多题目中经常被应用到,尤其是追求更好的时间复杂度的算法。

应用一 求一个递增数组中某个数值的数目。

比如1,1,2,4,4,4,5 这样的一列数组,4出现的个数。
这个问题传统的思路是从左到右依次依次线性查找,这样时间复杂度为o(n)。使用上面的二分查找的思路,可以分为两步分,首先找到检索值第一次出现的下标a,然后找到检索值最后依次出现的下标b,b-a+1就是所求的结果。这种思路用到了两次二分查找,不同是在array[mid]== token时并不是直接返回,而是存储到result变量中,同时分别改变low(low=mid+1)和high(high=low-1)的值(对应求最左和最右两种情况),继续loop,直到最终不满足low<=high而跳出循环,最终的result即为我们需要的最左(或者最右元素的index)

应用二 求循环数组的循环次数。

例如[3,4,5,1,2]可以看做[1,2,3,4,5]向右循环移动3次的结果,这个问题是根据循环后的结果求解循环次数。该问题可以转换为查找循环数组的最小值对应的index,正好是循环移位的次数。
解决思路同样是二分查找,只不过循环体中不仅仅根据mid进行判断,同时增加了两个值 pre 和next ,分别对应mid前一位和后一位的坐标。
代码如下:

def cal_times(a):
    length = len(a)
    low = 0
    high = length - 1
    while low<=high:
        mid = low+(high-low)//2
        if a[low]<=a[high]:
            return low
        prev = (mid-1+length)%length
        next = (mid+1)%length
        if a[mid]<a[prev] and a[mid]<a[next]:
            return mid
        elif a[mid]<a[low]:
            high = mid -1
        else:
            low = mid +1

是不是看起来非常清爽呢?

说一点点题外话和人生感悟,二分查找的思路也可以应用在我们生活中。当我们找不到通往人生目标的道路时,可以借鉴二分查找,把所有人生可能尝试的方向分成两大类,一类是和目标无关的领域,一类是可能相关的领域,无关的累赘的部分大胆的舍弃,然后在剩下的部分中继续探索,直到快速找到我们的通往目标的道路,这样比我们一个个都尝试一遍效率高很多。简而言之就是有不为才能有所为。人生在世,适当的做一些减法,抛弃一些身外之物,这样可以走的更快。

PS:感谢我的sweet heart 😘给我重新开启简书之旅的契机,你的陪伴是我坚持的动力。从今日开始,每天都写点东西,希望各位看客多多支持~😁

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,258评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,335评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,225评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,126评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,140评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,098评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,018评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,857评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,298评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,518评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,678评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,400评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,993评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,638评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,801评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,661评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,558评论 2 352

推荐阅读更多精彩内容