二分探索アルゴリズムを使用して数値の立方根を見つける Java プログラム
- WBOY転載
- 2023-08-28 13:33:10741ブラウズ
Cube root は整数値であり、それ自体を 3 回連続して乗算すると元の値になります。この記事では、二分探索を使用して数値の立方根を見つける Java プログラムを作成します。数値の立方根を求めることは、二分探索アルゴリズムの応用です。この記事では、二分探索を使用して立方根を計算する方法について詳しく説明します。
入出力例
リーリーたとえば、64 の立方根は 4 で、出力は 4 になります。
リーリーたとえば、216 の立方根は 6 で、出力は 6 になります。
二分探索
二分探索は、要素 (つまり、ソートされた配列内のキー) を見つけるために使用されるアルゴリズムです。バイナリアルゴリズムの動作原理は次のとおりです
配列が「arr」であると仮定します。配列を昇順または降順に並べ替えます。
low = 0、high = n-1 (n = 要素数) を初期化し、mid を middle = low (high-low)/2 として計算します。 arr[middle] == key の場合、配列の中央のインデックスである middle を返します。
キー値が arr[middle] 要素より小さい場合は、高インデックスを中間インデックス -1 に設定します。キー値が中間要素より大きい場合は、低インデックスを中間インデックスに設定します。 1
検索したい要素が見つかるまで二分探索を続けます。
low が high より大きい場合、キー値が配列 'arr' に存在しないため、直接 false を返します。
バイナリ検索を使用してキーを検索する例
＃＃＃質問＃＃＃順序付き整数配列 arr = [1, 3, 5, 7, 9, 11] の場合、二分検索を使用して要素のインデックス、つまり key = 7 を見つけます。
＃＃＃解決＃＃＃
low = 0、high = 5 (配列の最後のインデックス) を初期化します。
while ループの最初の反復により、中間インデックスが Mid = low (high-low)/2
となります。
中央値 = 0 (5-0)/2 = 2。
arr[mid] の値は 5 で、キー値 7 より小さくなります。したがって、low=mid1=3を更新します。
while ループの 2 回目の反復では、low (high-low)/2 を使用して、中間インデックス Mid = 4 を取得します。
arr[mid] の値は 9 で、キー値 7 より大きくなります。したがって、高 = 3 (中 - 1) を更新します。
while ループの 3 回目の反復により、中間インデックス Mid = 3 が得られます。
arr[mid] は 7 で、キーの値と同じです。したがって、中間のインデックスである 3 を返します。
つまり、指定された配列では、キーワードのインデックスは 7 であり、二分探索アルゴリズムを使用してインデックス 3 が見つかりました。
-
二分探索を使用して立方根を求めるアルゴリズム
- 数値「n」を考慮し、low=0 および right=n (指定された数値) を初期化します。
ステップ 2 - 中 = 低 (高-低)/2 を使用して、低値と高値の中央値を見つけます。
ステップ 3 -mid *mid*mid の値を見つけます。mid *mid*mid == n の場合、mid の値を返します。
ステップ 4 - 中央の値が n より小さい場合は、low=mid 1、それ以外の場合は high=mid-1
ステップ 5 - 値が見つかるまでステップ 2 ～ 4 を繰り返します。
Example の中国語訳は次のとおりです: Example
この例では、二分探索アルゴリズムを使用して値の立方根を見つけます。カスタム クラス「BinarySearchCbrt」を作成し、「cuberoot」関数で数値の立方根を見つけるための二分探索コードを実装しました。ここで、カスタム クラス オブジェクトを作成し、「number」という名前の整数変数を初期化し、そのクラス オブジェクトを使用して「cuberoot」関数を呼び出すことで、目的の出力が表示されます。
リーリー ＃＃＃出力＃＃＃ リーリー時間計算量: O(NlogN) 補助空間: O(1)
それでは、この記事では、Java の二分探索アルゴリズムを使用して数値の立方根を見つける方法について説明しました。
以上が二分探索アルゴリズムを使用して数値の立方根を見つける Java プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。