90％程序員寫(xiě)不出無(wú)BUG的二分查找程序？

要對(duì)有序表查找進(jìn)行用例設(shè)計(jì)，我們可以先分析輸入域，實(shí)際上有兩個(gè)輸入域，一個(gè)是要查找的數(shù)據(jù)，另外一個(gè)是有序表，可以先對(duì)有序表數(shù)據(jù)的個(gè)數(shù)進(jìn)行分類，有序表中可能有0，1，2，3，…個(gè)數(shù)據(jù)。因此我們可以將目標(biāo)數(shù)據(jù)分為以下幾個(gè)類：

完成第1級(jí)分類后，我們可以再對(duì)數(shù)據(jù)的特點(diǎn)進(jìn)行分類，因?yàn)橛行虮硎且粋€(gè)有順序的表，是有大小順序的，因此可以根據(jù)數(shù)據(jù)特點(diǎn)再進(jìn)行分類，以3個(gè)數(shù)據(jù)為例可以進(jìn)行以下分類：

有序表有0、1、2、4個(gè)以上數(shù)據(jù)的情況都可以按照以上的類似的方式進(jìn)行再分類。

當(dāng)按有序表中分類好后，可以再按要查找的數(shù)據(jù)進(jìn)行分類

當(dāng)對(duì)查找的數(shù)據(jù)和有序表分別分好類后，就可以把這兩種分類組合起來(lái)，比如將有序表有3個(gè)數(shù)據(jù)的分類情況和查找數(shù)據(jù)的分類情況組合起來(lái)就可以得到以下的分類：

組合完后，還需要將一些不可能或不需要的組合刪除掉，比如在3個(gè)數(shù)據(jù)都相等的情況下，查找數(shù)據(jù)介于集合兩個(gè)相鄰數(shù)據(jù)之間的情況就不存在，需要?jiǎng)h除掉這種情況，查找數(shù)據(jù)在有序表中的3種分類也由于集合中數(shù)據(jù)都相等而變成了一個(gè)分類，下圖便是3個(gè)數(shù)據(jù)都相等情況下的一個(gè)分類：

這樣7個(gè)最終分類減少到只有4個(gè)最終分類，查找數(shù)據(jù)為空的情況并不是所有情況下都需要測(cè)試的，其實(shí)只要測(cè)試有序表中有數(shù)據(jù)和沒(méi)有數(shù)據(jù)兩種情況就夠了，因此查找數(shù)據(jù)為空的情況如果在其他情況中有了分類，那么也可以將其刪去，這樣3個(gè)數(shù)據(jù)都相等的情況就只有3個(gè)最終分類，如下圖所示：

有序表有0個(gè)數(shù)據(jù)時(shí)可以所見(jiàn)成測(cè)試兩種情況，一種是查找的數(shù)據(jù)為空，一種是查找的數(shù)據(jù)不為空。

有序表中有1個(gè)數(shù)據(jù)時(shí)的分類可以縮減成以下3種分類情況：

有序表中有2個(gè)數(shù)據(jù)的分類可以縮減成以下8種分類：

這樣一來(lái)，即使不考慮4個(gè)以上數(shù)據(jù)以及3個(gè)數(shù)據(jù)在有兩個(gè)數(shù)據(jù)相等情況下的分類，總共的最終分類也有20多種，每種分類至少需要設(shè)計(jì)一個(gè)測(cè)試用例，總共至少需要20多個(gè)測(cè)試用例，一個(gè)簡(jiǎn)單的二分查找的測(cè)試用例都至少需要20多個(gè)，看到這里大家也許會(huì)明白為什么90％的專業(yè)程序員寫(xiě)不出一個(gè)無(wú)BUG的二分查找程序來(lái)。