binary search algorithm java implementation examples
このチュートリアルでは、Javaでのバイナリ検索と再帰的バイナリ検索について、そのアルゴリズム、実装、およびJavaバイナリSeachコードの例とともに説明します。
Javaでのバイナリ検索は、コレクション内のターゲット値またはキーを検索するために使用される手法です。これは、「分割統治」手法を使用してキーを検索する手法です。
キーの検索にバイナリ検索を適用するコレクションは、昇順で並べ替える必要があります。
通常、ほとんどのプログラミング言語は、コレクション内のデータの検索に使用される線形検索、バイナリ検索、およびハッシュ手法をサポートしています。後続のチュートリアルでハッシュについて学習します。
=> ゼロからJavaを学ぶには、ここにアクセスしてください。
学習内容：
Javaでのバイナリ検索
線形探索は基本的な手法です。この手法では、配列が順番にトラバースされ、キーが見つかるか、配列の最後に到達するまで、各要素がキーと比較されます。
線形検索は、実際のアプリケーションではめったに使用されません。バイナリ検索は、線形検索よりもはるかに高速であるため、最も頻繁に使用される手法です。
Javaには、バイナリ検索を実行する3つの方法があります。
PC用の最高の無料のYouTubeダウンローダー
- 反復アプローチの使用
- 再帰的アプローチの使用
- Arrays.binarySearch（）メソッドを使用します。
このチュートリアルでは、これら3つの方法すべてを実装して説明します。
Javaでのバイナリ検索のアルゴリズム
二分探索法では、コレクションは繰り返し半分に分割され、キーがコレクションの中央要素よりも小さいか大きいかに応じて、コレクションの左半分または右半分でキー要素が検索されます。
簡単な二分探索アルゴリズムは次のとおりです。
- コレクションの中間要素を計算します。
- キーアイテムをmid要素と比較します。
- key = middle要素の場合、見つかったキーの中間インデックス位置を返します。
- それ以外の場合、キー>中間要素の場合、キーはコレクションの右半分にあります。したがって、コレクションの下半分（右半分）で手順1〜3を繰り返します。
- その他のキー
上記の手順からわかるように、バイナリ検索では、最初の比較の直後にコレクション内の要素の半分が無視されます。
同じ手順のシーケンスが、反復および再帰的なバイナリ検索にも当てはまることに注意してください。
例を使用して、バイナリ検索アルゴリズムを説明しましょう。
例えば、次の10個の要素の並べ替えられた配列を取得します。
配列の中央の位置を計算してみましょう。
ミッド= 0 + 9/2 = 4
＃1）キー= 21
最高の無料のWindows10修復ソフトウェア
まず、キー値を(mid)要素と比較すると、mid = 21の要素値であることがわかります。
したがって、key = (mid)であることがわかります。したがって、キーは配列の4番目の位置にあります。
＃2）キー= 25
まず、キー値をmidと比較します。として（21<25), we will directly search for the key in the upper half of the array.
ここでも、配列の上半分の中央が見つかります。
ミッド= 4 + 9/2 = 6
場所(mid)の値= 25
次に、key要素とmid要素を比較します。したがって（25 == 25）、したがって、位置(mid) = 6でキーが見つかりました。
したがって、配列を繰り返し分割し、キー要素を中央と比較することで、どちらの半分でキーを検索するかを決定します。二分探索は、時間と正確さの点でより効率的であり、はるかに高速です。
二分探索実装Java
上記のアルゴリズムを使用して、反復アプローチを使用してJavaでバイナリ検索プログラムを実装しましょう。このプログラムでは、配列の例を取り上げ、この配列に対してバイナリ検索を実行します。
import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } } 出力：
入力配列：(5、10、15、20、25、30、35)
検索するキー= 20
要素はインデックスにあります：3
上記のプログラムは、二分探索の反復アプローチを示しています。最初に配列が宣言され、次に検索されるキーが定義されます。
配列の中央を計算した後、キーは中央の要素と比較されます。次に、キーがキーよりも小さいか大きいかに応じて、キーはそれぞれ配列の下半分または上半分で検索されます。
Javaでの再帰的二分探索
再帰手法を使用してバイナリ検索を実行することもできます。ここでは、キーが見つかるかリスト全体が使い果たされるまで、バイナリ検索メソッドが再帰的に呼び出されます。
再帰的二分探索を実装するプログラムを以下に示します。
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } } 出力：
入力リスト：(1、11、21、31、41、51、61、71、81、91
検索するキー：
キーは次の場所にあります：リストの3
Arrays.binarySearch（）メソッドを使用します。
JavaのArraysクラスは、指定された配列でバイナリ検索を実行する「binarySearch（）」メソッドを提供します。このメソッドは、検索する配列とキーを引数として受け取り、配列内のキーの位置を返します。キーが見つからない場合、メソッドは-1を返します。
次の例では、Arrays.binarySearch（）メソッドを実装しています。
import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } } 出力：
入力配列：(10、20、30、40、50、60、70、80、90)
検索するキー：50
キーは、配列のインデックス：4にあります。
よくある質問
Q＃1）二分探索をどのように記述しますか？
回答： 二分探索は通常、配列を半分に分割することによって実行されます。検索するキーがmid要素より大きい場合は、キーが見つかるまでサブ配列をさらに分割して検索することにより、配列の上半分を検索します。
同様に、キーがmid要素よりも小さい場合、キーは配列の下半分で検索されます。
Q＃2）二分探索はどこで使用されますか？
回答： バイナリ検索は、特にメモリスペースがコンパクトで限られている場合に、ソフトウェアアプリケーションでソートされたデータを検索するために主に使用されます。
Q＃3）二分探索の大きなOは何ですか？
回答： 二分探索の時間計算量はO（logn）です。ここで、nは配列内の要素の数です。二分探索の空間の複雑さはO（1）です。
Q＃4）バイナリ検索は再帰的ですか？
ハッシュテーブルの例c ++
回答： はい。二分探索は分割統治戦略の一例であり、再帰を使用して実装できるためです。配列を半分に分割し、同じメソッドを呼び出して、バイナリ検索を何度も実行できます。
Q＃5）なぜそれは二分探索と呼ばれるのですか？
回答： 二分探索アルゴリズムは、配列を半分または2つの部分に繰り返し分割する分割統治法を使用します。したがって、それは二分探索と呼ばれます。
結論
バイナリ検索は、Javaで頻繁に使用される検索手法です。バイナリ検索を実行するための要件は、データを昇順で並べ替える必要があることです。
バイナリ検索は、反復的アプローチまたは再帰的アプローチのいずれかを使用して実装できます。 JavaのArraysクラスは、Arrayでバイナリ検索を実行する「binarySearch」メソッドも提供します。
以降のチュートリアルでは、Javaでのさまざまな並べ替え手法について説明します。
=> ここで簡単なJavaトレーニングシリーズに注意してください。