[[398244]]

0.提要勾玄

本文主要先介紹查找的概念，然后介紹最簡(jiǎn)單的查找算法——順序查找，最后介紹二分查找。

1. 何為查找?

我們平常做很多事情，都會(huì)涉及到大量的增刪改查操作。比如一個(gè)用戶管理系統(tǒng)，會(huì)涉及用戶注冊(cè)(增)、用戶注銷(刪)、修改用戶信息(改)、查找用戶(查)，其中“刪”和“改”要依賴“查”操作。

下面重點(diǎn)來介紹一下查找這個(gè)重要的操作。

現(xiàn)給你一個(gè)點(diǎn)名冊(cè)，讓你查找一個(gè)學(xué)生。我們的做法是：根據(jù)這個(gè)學(xué)生的姓名或者學(xué)號(hào)，在點(diǎn)名冊(cè)中一個(gè)個(gè)的比對(duì)，直到找到一個(gè)學(xué)號(hào)或姓名符合條件的學(xué)生為止，否則就可以說點(diǎn)名冊(cè)中沒有該學(xué)生。

點(diǎn)名冊(cè)是一個(gè)集合，也可稱之為查找表，其中有大量同一類型的元素，也可稱之為記錄——學(xué)生。學(xué)生中可能有重名的，但不會(huì)有重學(xué)號(hào)的，也即，一個(gè)學(xué)號(hào)唯一對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)姓名可能對(duì)應(yīng)多個(gè)學(xué)生。如果我們根據(jù)學(xué)號(hào)找，只要點(diǎn)名冊(cè)中有，那么就可以找到唯一一個(gè)符合條件的學(xué)生。如果我們根據(jù)姓名找，那么我們就可能找到多個(gè)符合條件的學(xué)生。

像學(xué)號(hào)和姓名這種可以標(biāo)識(shí)一個(gè)學(xué)生的值，我們稱之為關(guān)鍵字，學(xué)號(hào)這種唯一標(biāo)識(shí)一個(gè)元素的值為主關(guān)鍵字，姓名這種可能標(biāo)識(shí)若干元素的值為次關(guān)鍵字。當(dāng)集合中的元素只有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，其關(guān)鍵字即為該數(shù)據(jù)元素的值。

比如數(shù)組[1, 2, 3, 4, 5, 6, 7, 8, 9]，其元素只有一個(gè)數(shù)據(jù)項(xiàng)，關(guān)鍵字即元素值本身;而點(diǎn)名冊(cè)中的元素——學(xué)生，卻有三個(gè)數(shù)據(jù)項(xiàng)——學(xué)號(hào)、姓名、專業(yè)，其中學(xué)號(hào)、姓名為關(guān)鍵字。

如果你學(xué)過數(shù)據(jù)庫，那么以上概念很容易理解。

所謂查找，通俗點(diǎn)說就是在一大群元素(集合 / 查找表)中，依照某個(gè)查找依據(jù)，找一個(gè)特定的、符合要求的元素(記錄)。

• 如果找到了，即查找成功，返回元素的信息;
• 如果找遍所有元素還沒找到，說明這群元素中沒有符合要求的元素，即查找失敗，返回一個(gè)可以明顯標(biāo)記失敗的值，比如“空記錄”或“空指針”。

所謂查找依據(jù)，就是給定一個(gè)目標(biāo)值，比較該目標(biāo)值和關(guān)鍵字是否相等。這就要求目標(biāo)值和關(guān)鍵字的類型要相同。

2. 順序查找(Sequential Search)

順序查找是我們最容易想到的查找方式，上面的點(diǎn)名冊(cè)例子中，查找一個(gè)學(xué)生就是用的就是順序查找。

順序查找思想：

從集合中的第一個(gè)元素開始至最后一個(gè)元素，逐個(gè)比較其關(guān)鍵字和目標(biāo)值。

• 若某個(gè)關(guān)鍵字和目標(biāo)值相等，則查找成功，返回所查元素的信息;
• 若沒有一個(gè)關(guān)鍵字和目標(biāo)值相等，則查找失敗，返回失敗標(biāo)識(shí)值。

比如，給定一個(gè)數(shù)組[11, 8, 4, 6, 9, 1, 16, 22, 14, 10]，給定目標(biāo)值 key，若找到，則返回其數(shù)組下標(biāo);否則，返回 -1：

只需從下標(biāo) 0 開始遍歷整個(gè)數(shù)組進(jìn)行比較即可：

/** 
 * @description: 從頭到尾遍歷整個(gè)數(shù)組，查找目標(biāo)值 key，返回其下標(biāo) index         
 * @param {int} *array 數(shù)組 為了說明問題簡(jiǎn)單，這里的數(shù)組元素不重復(fù) 
 * @param {int} length 數(shù)組長(zhǎng)度 
 * @param {int} key 目標(biāo)值 
 * @return {int} 如果找到，返回目標(biāo)值下標(biāo)；否則返回 -1 
 */ 
int sequential_search(int *array, int length, int key) 
{ 
    for (int index = 0; index < length; index++) { 
        if (array[index] == key) { 
            return index; 
        } 
    } 
    return -1; 
} 

以上代碼存在可優(yōu)化的地方，因?yàn)槊看伪容^之前要判斷數(shù)組是否越界：index < length，增加哨兵則可以避免這一步比較。

所謂哨兵，是一種形象的說法，將其放在數(shù)組頭或尾，用來標(biāo)記結(jié)束，當(dāng)遍歷到“哨兵”時(shí)，就說明數(shù)組中沒有目標(biāo)值，查找失敗。

為此，我們要特意在數(shù)組中留出一個(gè)位置給“哨兵”，并且把哨兵的值設(shè)置為目標(biāo)值：

像這樣，從另一側(cè)往“哨兵”一側(cè)遍歷。如果數(shù)組中有目標(biāo)值，則一定能找到;如果數(shù)組中沒有目標(biāo)值，那么就會(huì)遍歷至“哨兵”而停下，因?yàn)?ldquo;哨兵”的值就是目標(biāo)值，所以返回下標(biāo)為 0 時(shí)，意味著查找失敗。

/** 
 * @description: 順序查找改進(jìn)，增加哨兵 
 * @param {int} *array array[0] 不存放數(shù)據(jù)元素，充當(dāng)哨兵 
 * @param {int} length 數(shù)組長(zhǎng)度 
 * @param {int} key 目標(biāo)值 
 * @return {int} 返回0，即哨兵下標(biāo)，則查找失?。环駝t成功 
 */ 
int sequential_search_pro(int *array, int length, int key) 
{ 
    array[0] = key; // 哨兵 
    int index = length - 1; 
    while (array[index] != key) { 
        index--; 
    } 
    return index; 
} 

在一側(cè)放置“哨兵”的做法避免了每次遍歷進(jìn)行的數(shù)組越界檢查，這樣能提高效率。你可能會(huì)問就一句比較能提高多少效率?蚊子腿再小也是肉，而且當(dāng)數(shù)據(jù)量很多時(shí)，這些“蚊子腿”就會(huì)積累成“大象腿”了。

以上就是順序查找的基本內(nèi)容，雖然加了“哨兵”可以小小地優(yōu)化一下，但當(dāng)數(shù)據(jù)量極大時(shí)，仍然改變不了這種查找方法效率低下的事實(shí)。

因?yàn)槲覀兪菑囊活^到另一頭“順序遍歷”，所以有時(shí)候可能目標(biāo)值就在第一個(gè)位置，只查找一次就找到了，仿佛是天選之子;但有時(shí)候可能目標(biāo)值在最后一個(gè)位置，那就需要把所有元素都查找一遍才行，當(dāng)有千萬、億條數(shù)據(jù)時(shí)，這種就太可怕了。

當(dāng)然，優(yōu)點(diǎn)也有：算法簡(jiǎn)單好理解、適合數(shù)據(jù)量小的情況使用(使用時(shí)盡量把常用數(shù)據(jù)排在前面，這樣可以提高效率)。

3. 二分查找(Binary Search)

回到上面舉得那個(gè)點(diǎn)名冊(cè)的例子，那樣一個(gè)個(gè)地找學(xué)號(hào)或姓名實(shí)在是太慢了，有沒有什么更快的方法呢?

其實(shí)，在日常生活中的點(diǎn)名冊(cè)更多的是已排序的，比如按姓氏首字母、按學(xué)號(hào)大小排序，這樣一來，在找名字或找學(xué)號(hào)的時(shí)候就能有一個(gè)大致的區(qū)域了，而不必從頭到尾一個(gè)個(gè)地找。

所以，排好序的集合是便于查找的。下面介紹一種利用已排序的查找——二分查找(或折半查找)。

所謂二分查找，關(guān)鍵在“二分”“折半”上，顧名思義，不斷將集合進(jìn)行二分(折半)拆分，以此將集合拆分幾個(gè)區(qū)域，然后在某個(gè)區(qū)域中查找。前提條件是集合中的元素是有序的，元素必須采用順序表(數(shù)組)存儲(chǔ)。

二分查找思想：

在有序順序表中，取中間元素，將有序順序表分為左半?yún)^(qū)和右半?yún)^(qū)，比較中間元素的關(guān)鍵字和目標(biāo)值 key 是否相等：

1.如果相等，則查找成功，返回中間元素的信息;

2.如果不相等，說明目標(biāo)值 key 在左半?yún)^(qū)或右半?yún)^(qū)：

• 若目標(biāo)值 key小于中間元素的關(guān)鍵字，則來到左半?yún)^(qū);
• 若目標(biāo)值 key 大于中間元素的關(guān)鍵字，則來到右半?yún)^(qū);

不斷在各半?yún)^(qū)中重復(fù)上述過程，直到查找成功;否則，則集合中無目標(biāo)值，查找失敗。

下面結(jié)合實(shí)例，看一下具體過程。

這是一個(gè)有序的數(shù)組，我們要查找 33：

要想將數(shù)組分為左右半?yún)^(qū)，需要三個(gè)標(biāo)致：最左標(biāo)志位 left、最右標(biāo)志位 right和中間標(biāo)志位 mid。其中 mid = (left + right) / 2，確定了 mid 的值之后，與目標(biāo)值 key進(jìn)行比較：

中間值 28 小于目標(biāo)值key，說明目標(biāo)值在右半?yún)^(qū)，所以更新三個(gè)標(biāo)志位，進(jìn)入右半?yún)^(qū)，然后繼續(xù)比較：

中間值 39 大于目標(biāo)值key，更新三個(gè)標(biāo)志位，進(jìn)入左半?yún)^(qū)：

中間值 30 小于目標(biāo)值key，更新三個(gè)標(biāo)志位，進(jìn)入右半?yún)^(qū)：

中間值 33 等于目標(biāo)值key，返回其下標(biāo)，即 mid。

具體代碼如下：

/** 
 * @description: 二分查找 
 * @param {int} *array 有序數(shù)組 
 * @param {int} length 數(shù)組長(zhǎng)度 
 * @param {int} key 目標(biāo)值，和關(guān)鍵字比較 
 * @return {int} 返回目標(biāo)值下標(biāo)；若查找失敗，則返回 -1 
 */ 
int binary_search(int *array, int length, int key) 
{ 
    int left, mid, right; 
    left = 0; 
    right = length - 1; 
    while (left <= right) { 
        mid = (left + right) / 2; // 中間下標(biāo) 
        if (key < array[mid]) { // key 比中間值小 
            right = mid - 1; // 更新最右下標(biāo)，進(jìn)入左半?yún)^(qū) 
        } else if (key > array[mid]) { // key 比中間值大 
            left = mid + 1; // 更新最左下標(biāo)，進(jìn)入右半?yún)^(qū) 
        } else { 
            return mid; // key 等于中間值，返回其下標(biāo) 
        } 
    } 
    return -1; //未找到，返回 -1 
} 

二分查找的精髓在于中間標(biāo)志位 mid 把有序順序表一分為二，通過比較中間值和目標(biāo)值的大小關(guān)系，能夠篩選掉一半的數(shù)據(jù)，相當(dāng)于減少了一半的工作量。

上例只比較了四次，就找到了目標(biāo)值，如果使用順序查找，則需要八次。

可以看出，二分查找的效率相較于順序查找有了很大提高，但美中不足的是二分查找必須要求元素有序。在元素的有序狀態(tài)不變化或不經(jīng)常變化的情景下，二分查找非常合適;但是如果涉及到頻繁的插入和刪除操作，就意味著元素的有序狀態(tài)會(huì)被頻繁破壞，這樣一來，我們就不得不花精力去維護(hù)元素的有序狀態(tài)，自然又會(huì)降低效率，所以要根據(jù)實(shí)際情況靈活取舍。

以上就是順序查找和二分查找的內(nèi)容。

完整代碼請(qǐng)移步至 GitHub[1] | Gitee[2] 獲取。

參考資料

[1]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo

[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo