再帰的メソッドの比較を追跡するステートメントのインクリメント

Question

対象オブジェクトの類似オブジェクトのソートされた配列を検索する再帰バイナリ検索メソッドを構築しようとしています。これは、ソートされた配列のコレクションを検索し、コレクション内のすべての配列に共通の要素を検索する、より大きなアルゴリズムの一部です。目的は、アルゴリズムの検索/比較部分をできるだけ効率的にすることです。線形解が可能でなければならない。これはメソッドです：

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){ 
    boolean found = false; 
    int mid = first + (last - first)/2; 
    comparisons++; 
    if(first > last){ 
     found = false; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) == 0){ 
     found = true; 
     comparisons++; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) < 0) { 
     found = BinarySearch(ToSearch, ToFind, first, mid - 1); 
     comparisons++; 
    } 
    else{ 
     found = BinarySearch(ToSearch, ToFind,mid + 1, last); 
     comparisons++; 
    } 
    return found; 
} 

私が抱えている問題は、再帰による比較の回数を追跡することです。私はfalseとtrueに評価される比較を数えなければならないので、各選択ステートメント内に比較インクリメントステートメントを配置しようとしましたが、ステートメントがfalseと評価された場合ステートメントがインクリメントされないため、これは機能しません。私はまた、選択声明の間にそれらを置くことはできません。なぜなら、それは、もしエロスがなければ私に他のものを与えるからです検索のために再帰を使用するのは悪い考えですが、可能であると信じたいと思っています。どんな助けもありがとう。

Answer 1

おそらく、各ifブロックに変数を設定してそこに到達するのに必要な比較回数を設定し、最後に追加することができますか？

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){ 
    boolean found = false; 
    int newComparisons = 0; 
    int mid = first + (last - first)/2; 
    if(first > last){ 
     found = false; 
     newComparisons = 1; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) == 0){ 
     found = true; 
     newComparisons = 2; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) < 0) { 
     found = BinarySearch(ToSearch, ToFind, first, mid - 1); 
     newComparisons = 3; 
    } 
    else{ 
     found = BinarySearch(ToSearch, ToFind,mid + 1, last); 
     newComparisons = 3; 
    } 
    comparisons += newComparisons; 
    return found; 
}