0

これは私の二分探索です:

int binarySearch(int arr[], int value, int min, int max){
  int pos = -1;

  while (max >= min && pos == -1) {
    int mid = (max+min)/2;

    if(arr[mid] ==  value){
      pos = mid;
    }else if(arr[mid] < value){
      min = mid +1;
    }else if(arr[mid] > value){
      max = mid -1;
    }

  }
  return pos;
}

私はそれを次のように呼んでいます：

 //Arr contain values 0-63
int i = binarySearch(arr, 64, 0, 64);

これらは中間値です

32 48 56 60 62 63 64

最後のチェックで、配列の最後の位置が 63 のときに、位置 64 の要素にアクセスしようとしました。

私の実装の何が問題になっていますか?

4

3 に答える 3

3

配列には0〜63の値が含まれており（前述のとおり）、最小値と最大値に次の値を指定しています：最小= 0、最大= 64。次の行を変更して、コードが高い int 値を処理できるようにします。そうしないと、メモリ オーバーフローが発生する可能性があります。

       int mid = min+(max-min)/2;

上記の式は (max+min)/2 自体に単純化されますが、整数のオーバーフローは保護されます。

于 2012-10-28T19:49:49.173 に答える
0

このコードを試してください

while (max > min && pos == -1) {
    int mid = (max+min)/2;

    if(arr[mid] ==  value){
        pos = mid;
    }else if(arr[mid] < value){
        min = mid;
    }else if(arr[mid] > value){
        max = mid;
    }
}
于 2012-10-28T19:25:48.413 に答える
0

max==min の場合、長さは 0 なので、ループに入る必要はありません。あなたの最高水位が「最後を1回過ぎた」場合に条件を変更し(max > min && ...)ます（そして、あなたの最高水位はおそらく「最後を1回過ぎた」はずです。これは本当に便利なパターンです）

ああ、max は最後の要素ではなく「終わりの向こうの 1 つ」を表すため、max = midの代わりに作成します。max = mid-1

一般的なコーディング スタイルの改善として、この種のコードを実行する場合、toss はインデックスが範囲内にあることをアサートします。これにより、問題を早期に発見できるだけでなく、範囲内にある値とそうでない値を判断するのにも役立ちます...

于 2012-10-28T19:17:11.907 に答える