二進制搜索

Question

當在第2章（2.4.4）討論了Binary_Search，筆者提到， 「

注意變量不能聲明無符號（爲什麼？）。在案件 當無符號限定詞是有問題的，我們不會使用它。作爲 一個例子，如果無符號預選賽依賴數組不 從0開始，我們將放棄它。我們不會使用它。作爲 示例，如果無符號限定符依賴於從zer開始的不是 的數組o，我們會放棄它。我們也將避免使用 無符號類型作爲for循環中的計數器變量，因爲 通常會將循環計數器的方向從增加 更改爲遞減，而無符號限定符通常適用於前一種情況的 。例如，如果我聲明爲未簽名，則練習2.10中的代碼不會工作 。 」

的代碼如下：

int binary_search(input_type a[ ], input_type x, unsigned int n) 
{ 
int low, mid, high; /* Can't be unsigned; why? */ 
/*1*/ low = 0; high = n - 1; 
/*2*/ while(low <= high) 
{ 
/*3*/ mid = (low + high)/2; 
/*4*/ if(a[mid] < x) 
/*5*/ low = mid + 1; 
else 
/*6*/ if (a[mid] < x) 
/*7*/ high = mid - 1; 
else 
/*8*/ return(mid); /* found */ 
} 
/*9*/ return(NOT_FOUND); 
} 

問： 我無法理解的是，變量不能聲明unsigned.Why無符號限定符懷疑又如何不無符號預選賽增大，以減小改變循環計數器的方向是什麼？

Answer 1

如果mid是0，你想要的行high = mid - 1;將high設置爲-1，這將導致循環停止。

如果變量是無符號的，high會環繞到最大的無符號值，這會導致讀取超過緩衝區的末尾並可能崩潰。

至於這倒計時循環，下面的循環將永遠不會結束：

for (unsigned i = START_VAL; i >= 0; i--) {...} //WRONG 

因爲i是無符號，病情i >= 0將永遠是正確的。

Answer 2

本書的作者是錯誤的，似乎他是一個軟弱的程序員。:)

，首先它是一個壞主意，使用類型int作爲數組的大小。他應該使用類型size_t或至少在頭<stddef.h>限定，因爲陣列的大小的值可以是大於值類型int可容納類型ptrdiff_t。

考慮到，所有的C標準功能（如例如字符串函數），該處理陣列的尺寸限定出相應的參數爲具有類型size_t帳戶。

下面是標準功能bsearch的聲明。

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); 

的兩個參數，nmemb和size，具有類型size_t。

問題不在於用作數組大小類型的signed或unsigned int類型。問題是算法如何實現。

例如，他可以實現的算法，因爲它是在示範程序中顯示下列方式

#include <stdio.h> 

size_t binary_search(const int a[], int x, size_t n) 
{ 
    size_t low = 0, high = n; 

    while (low < high) 
    { 
     size_t middle = low + (high - low)/2; 

     if (a[middle] < x) 
     { 
      low = middle + 1; 
     } 
     else if (x < a[middle]) 
     { 
      high = middle; 
     } 
     else 
     { 
      return middle; 
     } 
    } 

    return n; 
} 

int main(void) 
{ 
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    size_t N = sizeof(a)/sizeof(*a); 

    for (int i = -1; i <= a[N - 1] + 1; i++) 
    { 
     printf("x = %d: %zu\n", i, binary_search(a, i, N)); 
    } 

    return 0; 
} 

程序輸出是

x = -1: 10 
x = 0: 0 
x = 1: 1 
x = 2: 2 
x = 3: 3 
x = 4: 4 
x = 5: 5 
x = 6: 6 
x = 7: 7 
x = 8: 8 
x = 9: 9 
x = 10: 10 

正如你看到的，如果一個值未找到數組然後函數返回等於數組大小的索引。

通常返回目標元素的索引的二進制搜索算法被定義爲下限算法。

下面是一個二分法搜索算法的實現示例，該算法返回目標元素存在或可能插入的較低位置。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 

size_t binary_search(const int a[], int x, size_t n) 
{ 
    size_t low = 0, high = n; 

    while (low < high) 
    { 
     size_t middle = low + (high - low)/2; 

     if (a[middle] < x) 
     { 
      low = middle + 1; 
     } 
     else 
     { 
      high = middle; 
     } 
    } 

    return high; 
} 

int main(void) 
{ 
    const size_t N = 10; 
    int a[N]; 

    srand((unsigned int)time(NULL)); 

    for (size_t i = 0; i < N; i++) 
    { 
     int value = rand() % (int)N; 

     size_t n = binary_search(a, value, i); 

     if (n != i) 
     { 
      memmove(a + n + 1, a + n, (i - n) * sizeof(int)); 
     } 

     a[n] = value; 

     for (size_t j = 0; j < i + 1; j++) 
     { 
      printf("%d ", a[j]); 
     } 
     putchar('\n'); 
    } 

    return 0; 
} 

程序輸出可能看起來像

8 
1 8 
1 5 8 
0 1 5 8 
0 1 5 5 8 
0 0 1 5 5 8 
0 0 1 2 5 5 8 
0 0 1 2 2 5 5 8 
0 0 1 2 2 5 5 8 9 
0 0 1 2 2 5 5 5 8 9 

正如你看到既未簽署int類型是在算法的實現中使用。

至於對方回答這個樣子

for (unsigned i = START_VAL; i >= 0; i--) {...} //WRONG 

然後再它只是寫不正確的循環。相反，在這種情況下，for循環的存在，應使用do-while循環，例如

unsigned i = START_VAL; 
do 
{ 
    // ... 
} while (i-- != 0);