二分查找
二分查找是著名粘我、高效并有應(yīng)用廣泛的查找算法魄梯。
二分常規(guī)實(shí)現(xiàn)
1.循環(huán)實(shí)現(xiàn)
下面我用python語言實(shí)現(xiàn)循環(huán)和遞歸二分查找有序線性表
2.遞歸實(shí)現(xiàn)
算法總結(jié)
二分查找要求遍歷的線性表采用順序存儲結(jié)構(gòu)，實(shí)現(xiàn)原理是算法使用兩個變量low和high档叔，并保證如果鍵在數(shù)組中則它一定在array[low...high]中程奠，然后方法進(jìn)入一個循環(huán)，不斷將數(shù)組的中間鍵（索引為mid）和被查找的鍵比較旦袋。如果被查找的鍵等于array[mid],返回mid骤菠。否則算法就縮小一半范圍，如果被查找的鍵小于array[mid],就繼續(xù)在左半邊查找疤孕，如果大于就在右半邊查找商乎。算法找到被查找的鍵或是查找范圍為空時該過程結(jié)束。二分查找之所以快是因?yàn)樗恍枰獧z查很小的條目（相對于數(shù)組的長度）就能夠找到目標(biāo)元素（或者確認(rèn)元素不存在）祭阀。在有序數(shù)組中進(jìn)行二分查找的時間復(fù)雜度為：O(log2n)
