二分查找算法

????????針對序列已經(jīng)排好序了惠窄,以從小到大排好的序列為例,每次取中間的元素和待查找的元素比較漾橙,如果中間的元素比待查找的元素小杆融,就說明“如果待查找的元素存在,一定位于序列的后半部分”霜运,這樣可以把搜索范圍縮小到后半部分脾歇,然后再次使用這種算法迭代。這種“每次將搜索范圍縮小一半”的思想稱為折半查找或二分查找(Binary Search)淘捡。

二分查找的條件是事先經(jīng)過排序藕各,且要求所有備查數(shù)據(jù)都必須加載到內存中進行。

每次變化的都是中間值焦除,這樣每次查找都會比上一次少一半的范圍激况,最多只需要比較log(n)+1次,時間復雜度為O(log(n))。使用二分查找就可以省去一半的遍歷乌逐。

故python實現(xiàn)代碼為

def binarysearch(L,number):

? ? start=0

? ? end=len(L)

? ? while start<=end :? ? ? ? ? ? ? ? ? ? ? ? ? ? #邊界條件范圍縮小到只有一個元素

? ? ? ? mid=(start+end)//2? ? ? ? ? ? ? ? ? ? ? ? #取中間位置

? ? ? ? if L[mid]<number:

? ? ? ? ? ? start=mid+1

? ? ? ? elif L[mid]>number:

? ? ? ? ? ? end=mid-1

? ? ? ? else:

? ? ? ? ? return mid

? ? return -1?

函數(shù)接受一個有序數(shù)組和一個指定查找的元素竭讳。如果該元素包含在數(shù)組中,這個函數(shù)將返回其位置黔帕。而我們所要跟蹤的就是每次要查找的數(shù)組范圍——開始時為整個數(shù)組代咸。

測試用例

>>>binarysearch([1,2,6,8,12,13],6)

2

>>>binarysearch ([1,2,6,8,12,13],7)

-1

>>>?

因為二分查找使用了分治思想,每個子問題的形式和解法都是相同的成黄,因為可以轉化為使用遞歸求解呐芥,如

defrecursionBS(L,number,start,end):

??? if start>end:

??????? return -1

??? mid=(start+end)//2

??? if L[mid]==number:

??????? return mid

??? elif L[mid]>number:

??????? returnrecursionBS(L,number,start,mid-1)

??? else:

??????? return recursionBS(L,number,mid+1,end)

測試用例

>>>recursionBS([1,2,6,8,12,13],6,0,6)

2

>>> recursionBS([1,2,6,8,12,13],8,0,6)

3

>>>recursionBS([1,2,6,8,12,13],1,0,6)

0

>>>recursionBS([1,2,6,8,12,13],13,0,6)

5

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市奋岁,隨后出現(xiàn)的幾起案子思瘟,更是在濱河造成了極大的恐慌,老刑警劉巖闻伶,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件滨攻,死亡現(xiàn)場離奇詭異,居然都是意外死亡蓝翰,警方通過查閱死者的電腦和手機光绕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來畜份,“玉大人诞帐,你說我怎么就攤上這事”ⅲ” “怎么了停蕉?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長钙态。 經(jīng)常有香客問我慧起,道長,這世上最難降的妖魔是什么册倒? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任蚓挤,我火速辦了婚禮,結果婚禮上驻子,老公的妹妹穿的比我還像新娘灿意。我一直安慰自己,他們只是感情好拴孤,可當我...
    茶點故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著甲捏,像睡著了一般演熟。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天芒粹,我揣著相機與錄音兄纺,去河邊找鬼。 笑死化漆,一個胖子當著我的面吹牛估脆,可吹牛的內容都是我干的。 我是一名探鬼主播座云,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼疙赠,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了朦拖?” 一聲冷哼從身側響起圃阳,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎璧帝,沒想到半個月后捍岳,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡睬隶,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年锣夹,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片苏潜。...
    茶點故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡银萍,死狀恐怖,靈堂內的尸體忽然破棺而出窖贤,到底是詐尸還是另有隱情砖顷,我是刑警寧澤,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布赃梧,位于F島的核電站滤蝠,受9級特大地震影響,放射性物質發(fā)生泄漏授嘀。R本人自食惡果不足惜物咳,卻給世界環(huán)境...
    茶點故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望蹄皱。 院中可真熱鬧览闰,春花似錦、人聲如沸巷折。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽锻拘。三九已至油吭,卻和暖如春击蹲,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背婉宰。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工歌豺, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人心包。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓类咧,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蟹腾。 傳聞我的和親對象是個殘疾皇子痕惋,可洞房花燭夜當晚...
    茶點故事閱讀 45,781評論 2 361

推薦閱讀更多精彩內容

  • 遞歸與二分查找算法 楔子 如果有這樣一個列表血巍,讓你從這個列表中找到66的位置,你要怎么做珊随? l = [2,3,5,...
    go以恒閱讀 755評論 0 0
  • 二分查找 二分查找只適用于有序的數(shù)組(list),每次查找的數(shù)據(jù)規(guī)模都為原來規(guī)模的一半述寡,直到找到為止。其時間復雜度...
    StephenZhang01閱讀 1,232評論 0 0
  • Knuth 大佬(發(fā)明 KMP 算法的那位)曾說: Although the basic idea of bina...
    盼旺閱讀 2,312評論 0 2
  • 麻木的胳膊叶洞,胃鲫凶,還有腦子 忽然想去街口偶遇你 伸手說:嗨 在一起去買今天的蔬菜 嫩綠的黃瓜 苗條的豆角 再去那家老...
    珊瑚的魚閱讀 54評論 3 1
  • 或許我該思考,重壓下的我衩辟,是選擇求穩(wěn)螟炫,還是選擇冒險,
    MissSad閱讀 214評論 0 0