Javaバイナリ検索で反復を実装する方法

1. 反復の概念

一連の命令または特定のステップを繰り返し実行することを反復と呼びます。平たく言えば、それらを1つずつ呼び出します。

このような過去をカウントする機能を実装したものをイテレータと呼びます。

2. 反復の 3 つの要素

1. 変数を決定する

反復アルゴリズムで解決できる問題では、少なくとも古い値から直接的または間接的に継続的に新しい値を推定する変数があり、この変数が反復変数です。

2. 関係を確立する

いわゆる反復関係とは、ある値の前の値から次の値を導き出す方法の式 (または関係) を指します。変数。反復関係の確立は反復問題を解決するための鍵であり、これは通常、再帰または後方推論を使用して達成できます。

3. プロセス制御

反復プロセスをいつ終了するか?これは、反復プログラムを作成するときに考慮する必要がある問題です。反復プロセスを際限なく繰り返すことはできません。反復処理の制御は、通常、必要な反復回数が一定の値で計算できる場合と、必要な反復回数が決定できない場合の 2 つの状況に分けられます。前者の場合、反復プロセスを制御するために固定数のループを構築できますが、後者の場合、反復プロセスを終了する条件をさらに分析する必要があります。

3. 二分探索の反復例

/*非递归的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}

各反復のコストはループ内のすべての作業に対して O(1) であるため、分析ではループの数を決定する必要があります。 。ループは right-left=leng-1 で開始され、right-left

以上がJavaバイナリ検索で反復を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。