バイナリ検索の比較とは何ですか？

Question

私は、与えられた数とソートされた配列に対してバイナリ検索アルゴリズムを実行するのに必要な比較回数を決定するプログラムを書いています。私が理解していないのは、比較の対象となるものです。

// returns the number of comparisons it takes to find key in sorted list, array 
    public static int binarySearch(int key, int[] array) { 
    int left = 0; 
    int mid; 
    int right = array.length - 1; 
    int i = 0; 
    while (true) { 
     if (left > right) { 
     mid = -1; 
     break; 
     } 
     else { 
     mid = (left + right)/2; 
     if (key < array[mid]) { 
      i++; 
      right = mid - 1; 
     } 
     else if (key > array[mid]) { 
      i++; 
      left = mid + 1; 
     } 
     else { 
      break; // success 
     } 
     } 
    } 
    return i; 
    } 

この関数は、配列内のキーを見つける際に行われた比較の総数と思われるiを返します。しかし、比較を定義するものは何ですか？条件付きがあるときはいつでもですか？

このコンセプトを理解しようとしてくれてありがとうございました。

Answer 1

通常、キーと配列要素を比較するたびに比較が行われます。しかし、コードはそれを数えていないようだ。検索境界の1つ（leftまたはright）が何回変更されたかをカウントしています。数えられるのは正確に同じものではありませんが、同じことにかなり近いです。境界がシフトされる回数は、ループの回数に直接関係し、したがって比較が行われる回数に直接関係しているからです。せいぜい、2つのカウント方法は1または2だけずれています（私はそれを正確に把握することはできませんでした）。一方は通常の定義を使用した場合、コードはkeyに等しい、より小さい、またはarray[mid]より大きかったか否かを決定するためにarray[mid]とkeyの単一の比較を行うInteger.compare(int,int)を使用するように書き換えることができること

も注意。

public static int binarySearch(int key, int[] array) { 
    int left = 0; 
    int mid; 
    int right = array.length - 1; 
    int i = 0; 
    while (left <= right) { 
     mid = (left + right)/2; 
     int comp = Integer.compare(key, array[mid]); 
     i++; 
     if (comp < 0) { 
      right = mid - 1; 
     } 
     else if (comp > 0) { 
      left = mid + 1; 
     } 
     else { 
      break; // success 
     } 
    } 
    return i; 
}