二分搜索 · 程序算法藝術與實踐

### 問題描述（來源于**《編程珠璣》第2版**的第2章第11頁問題A） Given a sequential file that contains at most four billion 32-bit integers in random order, find an integer that isn't in the file (and there must be at least one missing -- why?). How would you solve this problem with ample quantities of? main memory ? How would you solve it if you could use several external "scratch" files but only a few hundreds bytes of main memories ?　[譯]給定一個包含40億個隨機排列的順序文件，找到一個不在文件中的32位整數，在有足夠內存的情況下應該如何解決該問題？如果有幾個外部的臨時文件可用，但是僅有幾百字節的內存，又該如何解決？如有足夠內存，完全可用第一章介紹的位圖方法解決。這里關注內存不足時的解決方案。 ### 基本思想二分搜索（binary?search）又稱折半查找，它是一種效率較高的查找方法。二分查找要求：1）必須采用順序存儲結構； 2）必須按關鍵字大小有序排列。優缺點：折半查找法的優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。充分利用了元素間的次序關系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務。首先，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易于理解。第一個二分搜索算法早在1946 年就出現了，但是第一個完全正確的二分搜索算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。問題的關鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理后可以發現它的具體算法是很直觀的。 **分析** 對于32位的整數，可以表示的整數個數為2^32 = 4 294 967 296 > 4e9(40億)，因此有些數據不在該文件中。部分呼號約定：設存有40億數據的文件為F，其中每個數據均為32bit，不在該文件中的數據集合為M(just think about the word missing for a while)。F 中的數據和M中的數據一起構成32比特能夠表示的所有數據，即|F| + |M| = 2^32。從F中各數據的最高位比特開始，按其為0或者1分為兩部分，假設分別為A、B，則A、B的大小有兩種情況： 1) A和B中的數據個數相同。[由于|F| < 2^32，則|A| = |B| = |F|/2 < 2^31，]由于最初的數據文件F不包含數據M，則A、B均不包含M中的數據，即A、B中均缺失32比特能夠表示的”部分數據“(即M中的數據)，此時隨便找一個文件，比如A，設定其為新的F，同時假設A中缺失的數據為新的M(也就是先前M中以0開頭的數據，由于A 是以0開頭的數據，事實上M當然是未知的)，然后按照次高位比特進行劃分。 2) A和B中的數據個數不同。假設A的個數多余B中的個數，即|A| > |B|，不能確定A中是否缺失數據，因為A完全可能包含以0開頭的所有數據，這樣A就不缺失數據。但是可以確定的是B一定缺失數據，否則|B| = 2^31，總數為40億(小于2^32)，導致A中的數據小于2^31，進而少于于B中的數據個數，與開始處的假設矛盾。令B為新的F，B中缺失的數據位新的M(即M中以1打頭的數據，這也是由于B是以1開始的)。通過上述最高位比特的分析后，可以得到一個文件F，其數據規模不超過N/2，其中N位F中的所有數據。同時可知有些數據不在文件F中，僅在M中。接著按第二位比特的信心對F進行上述的A、B分類，A是F中第二位比特為0的數據，B是F中第二位比特為1的數據。也能得出A、B中數據個數的信息。 1、若|A| = |B|，即A、B缺失數據，令F為A即可，繼續。 2、若|A| != |B|，假設|A| > |B| ，則B缺失數據，令F為B，繼續。可以得到新的F其規模不超過N/4，繼續A、B分類 ### 示例模擬：一大堆的文字描述不好理解，下面以一組4bit數字模擬一下上面的過程：4bit共可表示2^4 = 16個整數，假設初始文件F如下： ~~~ 0 0000 1 0001 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 11 1011 12 1100 13 1101 14 1110 15 1111 ~~~ 前面一列為10進制數，可以看到文件中缺失了0010（2），1010（10）。 ### 第一次分解文件 A文件只包含0xxx的數：（x為未探索的位） ~~~ 0 0000 1 0001 3 0011 4 0100 5 0101 6 0110 7 0111 ~~~ B文件只包含1xxx的數： ~~~ 8 1000 9 1001 11 1011 12 1100 13 1101 14 1110 15 1111 ~~~ 按照上面的分析，|A|=|B|=7 < 2^3 ，都有數據缺失，隨機選取A文件為新的文件F。 ### 第二次分解文件 A文件只包含00xx的數： ~~~ 0 0000 1 0001 3 0011 ~~~ B文件只包含01xx的數： ~~~ 4 0100 5 0101 6 0110 7 0111 ~~~ 由于|A| < |B|，選取A為新的F文件。 ### 第三次分解文件 A文件只包含000x的數據： ~~~ 0 0000 1 0001 ~~~ B文件只包含001x的數據： ~~~ 3 0011 ~~~ 由于|B| < |A|，選取B為新的F文件。 ### 第四次分解文件 A文件只包含0010的數據：沒有數據。 B文件只包含0011的數據：0011 此時|A| < |B| ，所以缺失的數據必在A中，那么缺失的數據應該為0010，即十進制2。 ### 代碼 ~~~ #include <stdio.h> #include <stdlib.h> #define MAX_BIT 32 void file_split(FILE *srcfd, FILE *bit0fd, FILE *bit1fd, unsigned int *bit0_count, unsigned int *bit1_count, int cur_bit); /* binary search(0/1 search). For simplicity, ignore error checking */ int main(int argc, char**argv){ unsigned int mdata = 0; unsigned int bit0_count = 0; unsigned int bit1_count = 0; unsigned int missing_num = 0xFFFFFFFF; ? char mdatafn[] = "mdata.txt"; char bit0fn[] = "bit0.txt"; char bit1fn[] = "bit1.txt"; FILE *mdatafn_ptr = NULL; FILE *bit0_ptr = NULL; FILE *bit1_ptr = NULL; int cur_bit = MAX_BIT; mdatafn_ptr = fopen(mdatafn, "w+"); printf("Please input one number or input EOF to stop input:\n"); while(scanf("%u", &mdata) != EOF){ fprintf(mdatafn_ptr, "%u\n", mdata); printf("Please input one number or input EOF to stop input:\n"); } fflush(mdatafn_ptr); rewind(mdatafn_ptr); bit0_ptr = fopen(bit0fn, "w+"); bit1_ptr = fopen(bit1fn, "w+"); while(cur_bit-- > 0){ bit0_count = 0; bit1_count = 0; file_split(mdatafn_ptr, bit0_ptr, bit1_ptr, &bit0_count, &bit1_count, cur_bit); if(bit0_count <= bit1_count){ /* if |A| <= |B|, select A as new metadata */ printf("the missiong data's %d bit is 0.\n", cur_bit+1); missing_num &= (~(1<<cur_bit)); mdatafn_ptr = fopen(bit0fn, "r+"); bit0_ptr = fopen(mdatafn, "w+"); bit1_ptr = fopen(bit1fn, "w+"); } else{ /* if |B| < |A|, select B as new metadata */ printf("the missiong data's %d bit is 1.\n", cur_bit+1); missing_num |= (1<<cur_bit); mdatafn_ptr = fopen(bit1fn, "r+"); bit0_ptr = fopen(bit0fn, "w+"); bit1_ptr = fopen(mdatafn, "w+"); } if(0 == bit0_count || 0 == bit1_count){ break; } } fclose(mdatafn_ptr); fclose(bit0_ptr); fclose(bit1_ptr); unlink(mdatafn); unlink(bit0fn); unlink(bit1fn); printf("missing num is: %u\n", missing_num); return 0; } /* get every unsigned int number from file pointed by srcfd, * if it's single bit according cur_bit is 0, then write to file pointed * by bit0fd or else bit1fd return every sub-file's number of unsigned int */ void file_split(FILE *srcfd, FILE *bit0fd, FILE *bit1fd, unsigned int *bit0_count, unsigned int *bit1_count, int cur_bit){ char mdatastr[32] = {0,}; unsigned int mdata = 0; if(NULL == srcfd || NULL == bit0fd || NULL == bit1fd || NULL == bit0_count || NULL == bit1_count){ printf("invalid input parameter\n"); exit(-1); } while(fgets(mdatastr, 32, srcfd)){ mdata = strtoul(mdatastr, NULL, 10); if(mdata & 1<<cur_bit){ printf("put %08X to bit_1.txt.\n", mdata); fprintf(bit1fd, "%u\n", mdata); (*bit1_count)++; } else{ printf("put %08X to bit_0.txt.\n", mdata); fprintf(bit0fd, "%u\n", mdata); (*bit0_count)++; } memset(mdatastr, 0, sizeof(mdatastr)); } fclose(srcfd); fclose(bit0fd); fclose(bit1fd); } ~~~ 敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).