cs50 pset3バイナリ検索でwhileループに詰まっています

Question

whileループを使用してバイナリ検索を実装しようとしています。私が探しているのは、配列内にあるときに動作するようです。しかし、私が探しているintが存在しない場合、プログラムはループを塞ぐように見え、falseを返すことはありません。私はgdbを使用していますが、私はまだバグを把握していないようです。ご覧のとおり、if文などを追加して、これを理解しようとしています。

bool search(int value, int values[], int n) { 
    sort(values, n); 

    int begin = 0; 
    int end = (n - 1); 

    if (n < 1) { 
     return false; 
    } 
    while (end > begin + 1) { 
     int center = ((begin + end)/2); 
     if (values[0] == value) { 
      return true; 
     } 
     if (begin == value) { 
      return true; 
     } 
     if (end == value) { 
      return true; 
     } 
     if (end == (begin + 1) || end == begin) { 
      if (end == value || begin == value) { 
       return true; 
      } else { 
       return false; 
      } 
     } 
     if ((values[center]) == value) { 
      return true; 
     } else 
     if ((values[center]) > value) { 
      end = center; 
     } else 
     if ((values[center]) < value) { 
      begin = center; 
     } else { 
      return false; 
     } 
    } 
    // TODO: implement a searching algorithm 
    return false; 
} 

Answer 1

なぜこれを行うのですか？

if (values[0]==value) 
    { 
     return true; 
    } 
    if (begin == value) 
    { 
     return true; 
    } 
    if (end == value) 
    { 
     return true; 
    } 
    if (end == (begin+1) || end == begin) 
    { 
     if (end == value || begin == value) 
     { 
     return true; 
     } 
     else 
     { 
     return false; 
     } 
    } 

これらは必須ではありません。あなたがsort(values,n); を使用し、なぜあなただ​​け

while(end>beg+1 && values[center]!=value) 
    { 
    if ((values[center])>value) 
     end = center-1; 
    else if (values[center]<value) 
     begin = center+1; 
    center=(end+begin)/2; 
    } 
    if(values[center]==value) 
      return true; 
    else return false; 
    } 

以下など、私は理解していないんすることができ、それはC++のコードであれば、 sort(values,values+n); としてそれを使用して、Cのコードであるならば、任意の を使用して配列をソートアルゴリズムご使用のアレイ サイズおよび 時間に従ってください。 ありがとうございます。

Answer 2

この単純なことを不必要に複雑にしています。 あなたは自分のコードがあまりにも複雑であるあなたのコード内のすべての余分なものを削除して、この

`if ((values[center])==value) 
    { 
     return true; 
    } 
    else if ((values[center])>value) 
    { 
     end = center-1; 
    } 
    else if ((values[center])<value) 
    { 
     begin = center+1; 
    } 

`

Answer 3

を使用することができます。ここではいくつかのヒントがあります：

• 左のインデックスが含まれており、右のインデックスは除外してあなたが範囲を使用する必要があり、これはCで慣用され、単純なアルゴリズムにつながります。 startとendが非常に大きい場合

• あなたは潜在的な整数オーバーフローを避けるために、代わりにcenter = (start + end)/2;のcenter = start + (end - start)/2;を計算する必要があります。

• アレイのサイズはsize_tで、intより大きい可能性があります。

• 範囲の中央にある要素のそれと比較値：

  • 等しい場合、値が発見された、真を返します。
  • より小さい場合は、範囲を左部分に縮小し、中央を除外します。
  • それ以外の場合は、範囲を右側部分に縮小し、中央を除外します。

• 範囲が空で値が見つからなかった場合はfalseを返します。ここで

は簡単なバージョンです：

bool search(int value, int values[], size_t n) { 
    // Assuming values is sorted before calling this function 
    //sort(values, n); 

    size_t begin = 0; 
    size_t end = n; 

    while (begin < end) { 
     size_t center = begin + (end - begin)/2; 
     if (value == values[center]) { 
      return true; 
     } 
     if (value < values[center]) { 
      end = center; 
     } else { 
      begin = center + 1; 
     } 
    } 
    return false; 
}