バイナリ検索は

Question

、著者は述べている変数は符号なしで宣言することができないこと 「

お知らせ（理由例： 符号なし修飾子が0から始まる配列に依存していない場合は、破棄します。使用しません。 の例では、符号なし修飾子が配列に依存していない場合は、 は0から始まります私たちはそれを捨てる。 ループカウンタの方向を増やすのが一般的であるため、 が減少し、符号なしの修飾子が通常は の場合は前者の場合のみ変更されるため、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); 
} 

Q：？ 私は、変数は符号なし修飾子は疑問であるunsigned.Why宣言そして、どのようにすることができないことを理解することはできません符号なし修飾子はループカウンタの方向を増加から減少に変更しますか？

Answer 1

midが0の場合は、high = mid - 1;に設定してhighを-1に設定すると、ループが停止します。

変数が符号なしだった場合、highは最大の符号なしの値にラップアラウンドし、バッファの末尾を超えて読み込みが行われ、クラッシュする可能性があります。カウントダウンforループ用として

、次のループが終了することはありません：

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

をiが符号なしであるため、条件i >= 0は常にtrueになります。

Answer 2

本の著者が間違っていると、彼が弱いプログラマであるようだ。:)

まず第一に、配列のサイズとしてタイプintを使用することは悪い考えです。彼は配列size_tまたは少なくともptrdiff_tの型をヘッダ<stddef.h>で定義する必要があります。これは、配列のサイズの値が型intに対応できる値よりも大きい可能性があるためです。

配列サイズを扱うすべての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; 
} 

あなたはどちらの署名intタイプは、アルゴリズムの実装で使用されて見るとわかるように、プログラム出力は

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 

のように見えるかもしれません。その後、再び、それはちょうど間違って書かれているこの

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

のような他の回答に示すループ用として

。代わりに、この場合のforループの例と同様にdo-whileループが使用されなければならない

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