二分探索は、入力がソートされるときに適用される検索手法の 1 つです。ここでは、要素がすでにソートされているため、左に進むか右に進むかどうかの参照フレームとして機能する中央の要素を見つけることに焦点を当てています。この検索は、反復ごとに検索手法を最適化するのに役立ちます。バイナリ検索はバイナリ検索と呼ばれ、質問を解決する際に間接的に適用されるため、読者はストレスを感じます。
Java の二分探索アルゴリズム
以下は二分探索用に設計されたアルゴリズムです。
- 始める
- 入力配列とターゲットを取得します
- start = 0 および end = (配列サイズ -1) を初期化します。
- 中間変数をインド化する
- ミッド = (開始+終了)/2
- array[mid]==ターゲットの場合はmidを返します
- if 配列[mid]
- if array[mid]> target then end = mid-1
- start<=end の場合はステップ 5 に進みます。
- 要素が見つからない場合は -1 を返します
- 出口
ここで、入力がソートされていない場合、結果が未定義になったらどうなるかを考えているはずです。
注記： 重複がある場合、どれが見つかるかは保証されません。
Java バイナリ検索のメソッド
Java で実装するには 3 つのメソッドがあります 二分探索 Java では以下で説明します。
- 反復法
- 再帰的方法
- インビルドメソッド
1. Java での二分探索の反復法
以下に実装について説明します。
ジャワ
// Java implementation of iterative Binary Search> class> BinarySearch {> >// Returns index of x if it is present in arr[l....r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >while> (l <= r) {> >int> mid = (l + r) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x) {> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {>> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>出力
文字列メソッドJava
Element found at index 3>
ヒント： オタクの皆さんは、次のような機能があるかどうか疑問に思っているはずです。 lower_bound() または 上界（） おそらく C++ STL にあると思われます。したがって、正確な答えは、Java 9 までは機能がなく、その後に追加されたということです。
2. 二分探索の再帰的手法
上記のメソッドの実装を以下に示します。
ジャワ
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// Returns index of x if it is present in arr[l..> >// r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >if> (r>= l) {>> >int> mid = l + (r - l) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>出力
Element is present at index 3>
上記の方法の複雑さ
時間計算量: O(log N)
空間の複雑さ: O(1)、再帰呼び出しスタックが考慮される場合、補助空間は O(log N) になります。
3. Java での二分探索のビルド メソッドで
Arrays.binarysearch() プリミティブ データ型の配列でも機能します。
上記のメソッドの実装を以下に示します。
ジャワ
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>出力
22 found at index = 3 40 Not found>
Java コレクションでの二分検索
次に、Collections.binarySearch() が LinkedList に対してどのように機能するかを見てみましょう。基本的に、上で説明したように、このメソッドは ArrayList のようなランダム アクセス リストに対して log(n) 時間で実行されます。指定されたリストが RandomAccess インターフェイスを実装しておらず、サイズが大きい場合、このメソッドは O(n) 回のリンク トラバーサルと O(log n) 個の要素比較を実行する反復子ベースのバイナリ検索を実行します。
Collections.binarysearch() 次のようなオブジェクトコレクションに対して機能します 配列リスト そして リンクリスト 。
上記のメソッドの実装を以下に示します。
ジャワ
// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>出力
10 found at index = 3 15 Not found>
上記の方法の複雑さ
時間計算量 : O(log N)
補助スペース :O(1)