1. 理論基礎(chǔ)

當(dāng)我們要從一個(gè)序列中查找一個(gè)元素的時(shí)候，最快想到的方法就是順序查找法，但這種方法僅僅是暴力的把每個(gè)元素都排查一遍，元素個(gè)數(shù)少的時(shí)候還可以，一旦元素個(gè)數(shù)很多，效率就會(huì)非常低下。

1.1 概念

二分查找算法也叫折半查找算法。該算法要求數(shù)組數(shù)據(jù)要采用順序存儲(chǔ)有序排列，每次通過跟區(qū)間的中間元素對(duì)比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素。

1.2 前提條件

（1）查找的序列必須是有序的。有序是指所有元素是按照升序或降序排列好的，元素與元素之間的差值是隨機(jī)的。

（2）查找的元素只能是一個(gè)，不能實(shí)現(xiàn)多值查找。

1.3 基本思路

先找到有序序列的中間元素mid，然后拿它跟要找的目標(biāo)元素進(jìn)行對(duì)比，就可以初步判斷目標(biāo)元素的所在范圍，既然查找范圍已經(jīng)確定，則該范圍之外的元素就可以不用找了。按照上面的步驟反復(fù)查找下去直到找到目標(biāo)元素為止。

1.4 時(shí)間復(fù)雜度

二分查找每一次查找都可以縮減一半的查找范圍，則其時(shí)間復(fù)雜度為.

舉例：若共有2^32個(gè)元素，則采用二分查找最多32次就可以找到目標(biāo)，但是采用順序查找的方法最多需要查找4294967296次。

2 編程實(shí)現(xiàn)

寫在最后：文章是在學(xué)習(xí)過程中做的學(xué)習(xí)筆記，同時(shí)與志同道合者分享，文章內(nèi)容均經(jīng)過我自己實(shí)驗(yàn)證實(shí)可行，如有問題歡迎留言，很高興一起交流討論，共同進(jìn)步！