変更されたバイナリ検索配列

Question

EDIT：改善されたコードが含まれています。

現在のロジックが正しくありません。私は、整数 "wantToFind"を見つけるバイナリ検索をしたい、それが見つかるまで、配列にないなら、1からwantToFindを引きます。

これは、配列の最初の項目が最も低いwantToFind（見つけたい値）になることが保証されている大きなプログラムからこれを差し引いています。プログラムがまだな88

float list[15] = {60,62,64,65,67,69,71,72,74,76,77,79,81,83,84}; 

//binary search 
int wantToFind = 88; //other tests are 65, 61, 55 
bool itemFound = false; 

int current = 0; 
int low = 0; 
int high = 14; 

current = (low+high)/2; 
//int previousCurrent = -1; 

do { 
    do { 
     //if 61 < 72 
     if (wantToFind < list[current]) 
     { 
      //smaller 
      //previousCurrent = current; 
      high = current - 1; 
      current = (low+high/2); 
     } 
     else if (wantToFind > list[current]) 
     { 
      //bigger 
      //previousCurrent = current; 
      low = current + 1; 
      current = (low+high/2); 
     } 
     else{ 
      if(wantToFind == list[current]) 
      { 
       itemFound = true; 
      } 
     } 

    } while (low >= high); 

    if (itemFound == false) 
    { 
     wantToFind--; 
    } 
} while (itemFound == false); 

printf("\n%d", wantToFind); //which will be a number within the list? 
    return 0; 

}

Answer 1

私はあなたがほしいと思う理由を想像できませんwhile (low >= high)。これにより、最初にループが終了します。私はかなりあなたがwhile (low <= high)がほしいと確信しています。項目が見つからない場合

はまた、3つの可能性があります

1. wantToFindは、リスト内の最小の項目よりも小さいです。
2. wantToFindは、リスト内の最大アイテムよりも大きいです。
3. は、リストのどこかに配置されます。ケース2及び図3に

、内側ループの終了がwantToFindより小さい最初の項目が含まれているインデックスよりも1つ多くなりcurrentの値。上記ケース1内

、current点は、外側ループの必要はありませんということである0

に等しくなります。バイナリ検索が失敗すると、currentという値が挿入ポイントを示します。

また、アイテムが見つかったときに早めにやりたいと思うかもしれません。

最後に、do...whileをwhileループに変えてください。つまり：

while (!itemFound && low <= high) 

あなたは多くの理由を簡単に見つけることができます。

Answer 2

として高い数値を探していたときにあなたの終了条件がlow >= highあるべき立ち往生されるバイナリ検索規則を次のようにもかかわらず、しかし

、。それから、最初の価値が見つけられます。それは、目標とされるものよりも小さいか、または大きいものです（もちろん、あなたが実際に探しているもの）。次に、このif-statementはもう必要ありません：if (current < 0 || current > 14)しかし、ループの後で結果をチェック/調整する必要があります。