90％程序員寫不出無BUG的二分查找程序？

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

完成第1級分類后，我們可以再對數(shù)據(jù)的特點進行分類，因為有序表是一個有順序的表，是有大小順序的，因此可以根據(jù)數(shù)據(jù)特點再進行分類，以3個數(shù)據(jù)為例可以進行以下分類：

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

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

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

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

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

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

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

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

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