二分搜索(binary search),也叫做 折半搜索(half-interval search),對(duì)數(shù)搜索(logarithmic search),對(duì)半搜索(binary chop),是一種在有序數(shù)組中查找某一特定元素的搜索算法.

二分搜索有幾個(gè)變體.特別是,分散層疊(fractional cascading)(將每個(gè)數(shù)組里的值集合成一個(gè)數(shù)組,元素為11[0,3,2,0] 的形式,括號(hào)內(nèi)的數(shù)字是該值在對(duì)應(yīng)數(shù)組中應(yīng)該返回的數(shù)字)提高了在多個(gè)數(shù)組中查找相同值的效率,高效的解決了一系列計(jì)算幾何和其他領(lǐng)域的查找問題).指數(shù)查找(Exponential search)延伸了二分查找到一個(gè)沒有邊界的 list.binary search tree和B-tree是基于 binary search 延伸的.

原理

搜索時(shí)從數(shù)組中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結(jié)束;如果中間元素大于或者小于要查找的元素,則在數(shù)組中大于或者小于查找元素的一半中繼續(xù)查找,重復(fù)這個(gè)過程直到找到這個(gè)元素,或者這一半的大小為空時(shí)則代表找不到.這樣子每一次比較都使得搜索范圍縮小一半.

步驟

給定一個(gè)有序數(shù)組 A 是 A0,...,An-1并保證 A0<=...<=An-1,以及目標(biāo)值 T.

1. 令 L 為0,R 為 n-1.
2. 如果 L>R 則搜索失敗
3. 令m(中間值元素索引)為最大的小于(L+R)/2的整數(shù)
4. 如果 Am<T ,令 L=m+1并回到第2步;
5. 如果 Am>T ,令 R=m-1并回到第2步;
6. 當(dāng) Am=T,搜索結(jié)束;T 所在的索引位置為m.

變體

1. 令 L 為0,R 為 n-1.
2. 令 m(中間元素索引) 為上限,也就是最小的大于(L+R)/2的值.
3. 如果 Am>T ,設(shè)置 R 為 m-1并且返回第2步
4. 如果 Am<=T ,設(shè)置 L 為m 并且返回第2步.
5. 直到 L=R ,搜索完成.這時(shí)候如果T=Am,返回 m,否則,搜索失敗.

在 Am<=T 的時(shí)候,這個(gè)變體將 L 設(shè)置為 m 而不是 m+1.這個(gè)方式的比較是更快速的,因?yàn)樗诿總€(gè)循環(huán)里省略了一次比較.但是平均就會(huì)多出來一次循環(huán).在數(shù)組包含重復(fù)的元素的時(shí)候這個(gè)變體總是會(huì)返回最右側(cè)的元素索引.比如 A 是[1,2,3,4,4,5,6,7]查找的對(duì)象是4,那么這個(gè)方法會(huì)返回 index 4,而不是 index 3.

大致匹配

由于有序數(shù)組的順序性,可以將二分搜索擴(kuò)展到大致匹配.可以用來計(jì)算賦值的排名(或稱秩,比它更小的元素的數(shù)量),前趨(下一個(gè)最小元素),后繼(下一個(gè)最大元素)以及最近鄰.還可以使用兩個(gè)排名查詢來執(zhí)行范圍查詢.

• 排名查詢可以使用調(diào)整后的二分搜索來進(jìn)行.成功時(shí)返回m,失敗時(shí)返回 L, 這樣就等于返回了比目標(biāo)值小的元素?cái)?shù)目.
• 前趨和后繼可以使用排名查詢來進(jìn)行.當(dāng)知道目標(biāo)值的排名,成功時(shí)前趨是排名位置的上一個(gè)元素,失敗時(shí)則是排名位置的元素.它的后繼是排名位置的后一個(gè)元素,或是前趨的下一個(gè)元素.目標(biāo)值的最近領(lǐng)可能是前趨或后繼,取決于哪個(gè)更接近目標(biāo)值.
• 范圍查詢,一旦知道范圍兩邊的值的排名,那么大于邊界最小值且小于邊界最大值的元素排名就是他們的范圍,是否包含邊界值根據(jù)需要處理.

性能分析

時(shí)間復(fù)雜度
二分查找每次把搜索區(qū)域減少一半,時(shí)間復(fù)雜度為

(n 是集合中元素的個(gè)數(shù))
最差的情況是 遍歷到最后一層,或者是沒有找到該元素的時(shí)候,復(fù)雜度為 .

綜合復(fù)雜度為

分散層疊(fractional cascading) 可以提高在多數(shù)組中查詢相同值的效率. k 是數(shù)組的數(shù)量,在每個(gè)數(shù)組中查詢目標(biāo)值消耗 的時(shí)間.分散層疊可以將它降低到 .

變體效率分析
相對(duì)于正常的二分搜索,它減少了每次循環(huán)的比對(duì)次數(shù),但是它必須做完完整的循環(huán),而不會(huì)在中間就得到答案.但是在 n 很大的情況下減少了對(duì)比次數(shù)的提升不能夠抵消多余的循環(huán)的消耗.

空間復(fù)雜度
O(1).尾遞歸,可以改寫為循環(huán).

應(yīng)用

查找數(shù)組中的元素,或用于插入排序.

二分搜索和其他的方案對(duì)比

使用二分搜索的有序數(shù)組在插入和刪除操作效率很低,每個(gè)操作消耗 O(n) 的時(shí)間.其他的數(shù)據(jù)結(jié)構(gòu)提供了更高效的插入和刪除,并且提供了同樣高效的完全匹配.然而,二分搜索適用于很多的搜索問題,只消耗 的時(shí)間.

Hashing

對(duì)于關(guān)聯(lián)數(shù)組 (associative arrays),哈希表 (hash tables),他們是通過hash 函數(shù)將鍵映射到記錄上的數(shù)據(jù)結(jié)構(gòu),通常情況下比在有序數(shù)組的情況下使用二分查找要更快.大部分的實(shí)現(xiàn)平均開銷都是常量級(jí)的.然而, hashing 并不適用于模糊匹配,比如計(jì)算前趨,后繼,以及最近的鍵,它在失敗的查詢情況下能給我們的唯一信息就是目標(biāo)在記錄中不存在.二分查找是這種匹配的理想模式,消耗對(duì)數(shù)級(jí)別的時(shí)間.

Trees

二叉搜索樹(binary search tree) 是一個(gè)基于二叉搜索原理的二叉樹(binary tree)數(shù)據(jù)結(jié)構(gòu).樹的記錄按照順序排列,并且每個(gè)樹里的每個(gè)記錄都可以使用類似二叉搜索的方法來搜索,平均耗費(fèi)對(duì)數(shù)級(jí)的時(shí)間.插入和刪除的平均時(shí)間也是對(duì)數(shù)級(jí)的.這會(huì)比有序數(shù)組消耗的線性時(shí)間要快,并且二叉樹擁有所有有序數(shù)組可以執(zhí)行的操作,包含范圍和模糊查找.

然而二叉搜索通常情況下比二叉搜索樹的搜索更有效率,因?yàn)槎嫠阉鳂浜芸赡軙?huì)完全不平衡,導(dǎo)致性能稍差.這同樣適用于 平衡二叉搜索樹( balanced binary search trees) , 它平衡了它自己的節(jié)點(diǎn)稍微向完全平衡樹靠攏.雖然不太可能,但是樹有可能只有少數(shù)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)導(dǎo)致嚴(yán)重不平衡,這種情況下平均時(shí)間損耗和最差的情況差不多都是 O(n) .二叉搜索樹比有序數(shù)組占用更多的空間.

二叉搜索樹因?yàn)榭梢愿咝У脑谖募到y(tǒng)中結(jié)構(gòu)化,所以他們可以在硬盤中進(jìn)行快速搜索.B-tree 泛化了這種樹結(jié)構(gòu)的方法.B-tree 常用于組織長(zhǎng)時(shí)間的存儲(chǔ)比如數(shù)據(jù)庫(databases)和文件系統(tǒng)(filesystems).

Linear search

線性搜索( Linear Search)是一種簡(jiǎn)單的搜索算法,它查找每一個(gè)記錄直到找到目標(biāo)值.線性搜索可以在 鏈表(linked list) 上使用,它的插入和刪除會(huì)比在數(shù)組上要快.二分搜索比線性搜索要快除非數(shù)組很短.如果數(shù)組必須先被排序,這個(gè)消耗必須在搜索中平攤.對(duì)數(shù)組進(jìn)行排序還可以進(jìn)行有效的近似匹配和其他操作.

Set membership algorithms

一個(gè)和搜索相關(guān)的問題是集合成員(set membership).所有有關(guān)查找的算法,比如二分搜索,都可以用于集合成員.還有一些更適用于集合成員的算法,位數(shù)組(bit array)是最簡(jiǎn)單的一個(gè),在鍵的范圍是有限的時(shí)候非常有用.它非扯梗快,是需要O(1)的時(shí)間.朱迪矩陣(Judy array)可以高效的處理64位鍵.

對(duì)于近似結(jié)果,布隆過濾器(Bloom filters)是另外一個(gè)基于哈希的概率性數(shù)據(jù)結(jié)構(gòu),通過存儲(chǔ)使用bit array 和多重 hash 函數(shù)編碼的鍵集合. Bloom filters 在大多數(shù)情況下空間效率比bit arrays 要高而不會(huì)慢太多:使用了 k 重hash 函數(shù),成員查找只需要 O(k) 的時(shí)間.然而, Bloom filters 有一定的誤判性.

其他的數(shù)據(jù)結(jié)構(gòu)

這里存在一些數(shù)據(jù)結(jié)構(gòu)在某些情況下比在有序數(shù)組上使用二分搜索進(jìn)行查找或其他的操作更加高效.比如,在van Emde Boas trees, fusion trees, 前綴樹(tries), 和位數(shù)組 上進(jìn)行查找,近似匹配,以及其他可用的操作可以比在有序數(shù)組上進(jìn)行二分搜索更加的高效.然而,盡管這些操作可以比在無視鍵的情況下比有序數(shù)組上使用更高效,這樣的數(shù)據(jù)結(jié)構(gòu)通常是因?yàn)槔昧四承╂I的屬性(鍵通常是一些小整數(shù)),因此如果鍵缺乏那些屬性將會(huì)消耗更多的空間或時(shí)間.一些結(jié)構(gòu)如朱迪矩陣,使用了多種方式的組合來保證效率和執(zhí)行近似匹配的能力.

變體

Uniform binary search

Uniform binary search 不是存儲(chǔ)下限和上限的邊界值,而是中間元素的索引,和從這次循環(huán)的中間元素到下次循環(huán)的中間元素的變化.每一步的變化減少一半.比如,要搜索的數(shù)組是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],中間元素是6.Uniform binary search 同時(shí)對(duì)左邊和右邊的子數(shù)組進(jìn)行操作.在這個(gè)情況下,左邊的子數(shù)組([1, 2, 3, 4, 5]) 的中間元素 3 而右邊的子數(shù)組 ([7, 8, 9, 10, 11]) 的中間元素是 9.然后存儲(chǔ)3 作為兩個(gè)中間元素和 6 的差別.為了減少搜索的空間使用,算法同時(shí)加上或減去這個(gè)和中間元素的改變.這個(gè)算法的好處是可以將每次循環(huán)的索引的差別存儲(chǔ)到一個(gè)表里,在某些系統(tǒng)里可以提高算法的性能.

image

Exponential search

指數(shù)查找(Exponential Search)將二分搜索拓展到無邊界數(shù)組.它最開始尋找第一個(gè)索引是2的冪次方并且要比目標(biāo)值大的元素的索引.然后,它將這個(gè)元素索引設(shè)置為上邊界,然后開始二分搜索.指數(shù)查找消耗 次循環(huán) ,然后二分搜索消耗 次循環(huán), x 是目標(biāo)值的位置.指數(shù)查找適用于有界列表,在目標(biāo)值接近數(shù)組開始的位置的時(shí)候比二分查找性能有所提高.

image

Interpolation search

內(nèi)插搜索(Interpolation search)忽略了目標(biāo)值的位置,計(jì)算數(shù)組的最低和最高元素的距離即數(shù)組的長(zhǎng)度.這只有在數(shù)組元素是數(shù)字的時(shí)候才能使用.它適用于中間值不是最好的猜測(cè)選擇的情況.比如,如果目標(biāo)值接近數(shù)組的最高元素,最好是定位在數(shù)組的末端.如果數(shù)組的分布是均勻的或者接近均勻的,它消耗 次比較.

實(shí)際上,內(nèi)插搜索在數(shù)組元素較少的情況下是比二分搜索更慢的,因?yàn)閮?nèi)插搜索需要額外的計(jì)算.盡管它的時(shí)間復(fù)雜度增長(zhǎng)是小于二分搜索的,只有在在大數(shù)組的情況下這個(gè)計(jì)算的損耗可以被彌補(bǔ).

image

Fractional cascading

分散層疊(Fractional cascading) 可以提高在多個(gè)有序數(shù)組里查找相同的元素或近似匹配的效率,分別在每個(gè)數(shù)組里查找總共需要 的時(shí)間, k 是數(shù)組的數(shù)量.分散層疊通過將每個(gè)數(shù)組的信息按指定的方式存儲(chǔ)起來將這個(gè)時(shí)間降低到 .

它將每個(gè)數(shù)組里的值集合成一個(gè)數(shù)組,元素為 11[0,3,2,0] 的形式,括號(hào)內(nèi)的數(shù)字是該值在對(duì)應(yīng)數(shù)組中應(yīng)該返回的數(shù)字)提高了在多個(gè)數(shù)組中查找相同值的效率,高效的解決了一系列計(jì)算幾何和其他領(lǐng)域的查找問題

分散層疊被發(fā)明的時(shí)候是為了高效的解決各種計(jì)算幾何學(xué)(computational geometry) 問題,但是它同樣適用于其他地方,例如 數(shù)據(jù)挖掘(data mining) 和 互聯(lián)網(wǎng)協(xié)議(Internet Protocal) 等.

實(shí)現(xiàn)時(shí)的問題

要注意中間值的取值方法,如果使用 (L+R)/2 當(dāng)數(shù)組的元素?cái)?shù)量很大的時(shí)候回造成計(jì)算溢出.所以要使用L+(R-L)/2.

示例

C 版本- 遞歸

int binary_search(const int arr[], int start , int end , int khey){
    if (start > end)
      return -1;

    int mid = start +(end - start)/2;   //直接平均可能會(huì)溢位,所以用此算法
    if (arr[mid] > khey)
        return binary_search(arr , start , mid - 1 , khey);
    else if (arr[mid] < khey)
        return binary_search(arr , mid + 1 , end , khey);
    else
        return mid;    //最后才檢測(cè)相等的情況是因?yàn)榇蠖鄶?shù)搜尋情況不是大于就是小于

}

C 版本- while 循環(huán)

int binary_search(const int arr[], int start, int end, int khey){
    int result = -1;    //如果沒有搜索到數(shù)據(jù)返回 -1

    int mid;
    while (start <= end){
      mid = start + (end - start)/2 ;    //直接平均可能會(huì)溢位,所以用此算法
      if (arr[mid] > khey)
          end = mid-1;
      else if (arr[mid] < khey)
          start = mid + 1;
      else{    //最后才檢測(cè)相等的情況是因?yàn)榇蠖鄶?shù)搜尋情況不是大于就是小于
          result = mid;
          break;
      }
    }

    return result;

}

Python3 遞歸

def binary_search(arr, start, end, hkey):
    if start > end:
        return -1

    mid = start + (end - start) / 2
    if arr[mid] > hkey:
        return binary_search(arr, start , mid - 1,hkey)
    if arr[mid] < hkey:
        return binary_search(arr, mid + 1, end, hkey)
    return mid

Python3 while 循環(huán)

def binary_search(arr, start, end, hkey):
    result = -1

    while start <= end:
        mid = start + (end - start) / 2
        if arr[mid] > hkey :
            end = mid - 1
        elif arr[mid] < hkey :
            start = mid + 1
        else :
            result = mid
            break

    return result

Java 遞歸

public static int binarySearch(int[] arr, int start, int end, int hkey){
    if (start > end)
        return -1;

    int mid = start + (end - start)/2;    //防止溢位
    if (arr[mid] > hkey)
        return binarySearch(arr, start, mid - 1, hkey);
    if (arr[mid] < hkey)
        return binarySearch(arr, mid + 1, end, hkey);
    return mid;  

}

Java while 循環(huán)

public static int binarySearch(int[] arr, int start, int end, int hkey){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > hkey)
            end = mid - 1;
        else if (arr[mid] < hkey)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }

    return result;

}

About Me

我的 GitHub https://github.com/LeonChen1024