二分搜索

一，查找

顧名思義就是大家常說(shuō)的增刪改查中的查，想要在某一個(gè)數(shù)據(jù)結(jié)構(gòu)內(nèi)查找某個(gè)元素。

二，二分搜索思想

二分搜索其實(shí)就是二分查找。

1. 取搜索序列的中間元素為此次搜索的對(duì)比元素，與待搜索元素進(jìn)行比較。如搜索序列有偶數(shù)個(gè)元素，那么可以以中間兩個(gè)元素的其中一個(gè)作為此次對(duì)比元素，通常選左邊那個(gè)

2. 如果此次對(duì)比元素較大，說(shuō)明搜索元素只能在這個(gè)對(duì)比元素的左側(cè)，對(duì)左側(cè)序列繼續(xù)進(jìn)行二分搜索

3. 如果此次對(duì)比元素較小，那么搜索元素只能在這個(gè)對(duì)比元素的右側(cè)，對(duì)右側(cè)序列繼續(xù)進(jìn)行二分搜索

4. 如果此次對(duì)比元素與搜索元素相等，那么搜索成功了。

5. 直到初識(shí)序列完成遞歸，然而還是沒(méi)有搜索成功，那么此序列中便沒(méi)有這個(gè)搜索元素，意味著搜索失敗。

三，性能

因?yàn)槎炙阉魇∪チ撕芏嗖槐匾谋容^，直接從大或小的序列中進(jìn)行下次搜索，所以性能還是比較好的

通過(guò)查找樹(shù)容易發(fā)現(xiàn)，時(shí)間復(fù)雜度是O(log2(n))

四，適用情況

此方法只能對(duì)已經(jīng)有序的序列進(jìn)行使用。