バイナリ検索でエラーが発生しましたJava

Question

このバイナリ検索で何が問題なのかわかりました。コメントアウトされた行があり、これまで必要だったとは思っていないので、私が考えることができるのはその行を削除することだけです。それ以外に、私は何かが欠けていると思うことはできません - 間違っていることが本当に明白なものがありますか？

public boolean search(int val) { 
    int low = 0; 
    int high = size-1; 
    int middle = -1; 
    boolean found = false; 
    while (!found && low < high) { 
     middle = low + (high-low)/2; 
     if (a[middle] == val) 
      found = true; 
     else if (a[middle] < val) 
      low = middle + 1; 
     else // (a[middle] > val) 
      high = middle - 1; 
    } 
    return found; 
} 

Answer 1

あなたは、アレイ内の2つの値を持っているときのケースを見てみましょう：

int low = 0; 
int high = size-1; // high = 1 
int middle = -1; 
boolean found = false; 
while (!found && low < high) { 
    middle = low + (high-low)/2; // middle = 0 + (1-0)/2 = 0 
    if (a[middle] == val) // FALSE (because a[0] = 0) 
     found = true; 
    else if (a[middle] < val) // TRUE (because a[0] = 0 and 0 < 1) 
     low = middle + 1; // low = 0 + 1 = 1 
    else // (a[middle] > val) 
     high = middle - 1; 
} 
return found; 

1 =低いので、あなたがから抜け出す：[0、1]あなたが値1を探しのコードを実行してみましょうこのループは条件がlow < highで、配列に1が入っていてもfalseを返します。

middle = low + (high-low)/2;はintを使用しており、切り捨てられるという問題が原因です。

Answer 2

で行くと読むことがあなたのコードをより簡単にできます...

middle = low + (high-low)/2; 
if (a[middle] == val) { 
    found = true; 
    break; 
} 

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

私は今、それが明確になると思いますが、そのコメントは本当に何を言っている - それは単にこれが場合であることを表します[中]> val。

Answer 3

検索する配列を[1,2]にしてください。

は、コードを歩く：

スタート：low = 0, high = 1。 ステップ1：middle = 0 - 一致しない（1 < 2）so low = 1。 ループチェック - low < high？ NO - 検索を停止します。