Java の Arrays.binarySearch() と例 |セット1
Arrays.binarySearch() このメソッドは、二分探索アルゴリズムを使用して、指定されたデータ型の指定された配列で指定された値を検索します。配列は次のようにソートする必要があります。 配列.sort() この呼び出しを行う前にメソッドを実行します。ソートされていない場合、結果は不定になります。配列に指定された値を持つ複数の要素が含まれている場合、どれが見つかるかという保証はありません。以下に示す図をざっと見てみましょう。
図：
Searching for 35 in byteArr[] = {10,20,15,22,35} will give result as 4 as it is the index of 35 Searching for g in charArr[] = {'g','p','q','c','i'} will give result as 0 as it is the index of 'g' Searching for 22 in intArr[] = {10,20,15,22,35}; will give result as 3 as it is the index of 22 Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5} will give result as -1 as it is the insertion point of 1.5 Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f} will give result as -5 as it is the insertion point of 35.0 Searching for 5 in shortArr[] = {10,20,15,22,35} will give result as -1 as it is the insertion point of 5 これは、Java でソートされた配列内の要素を見つけるための最も単純かつ効率的な方法です。
構文：
public static int binarySearch(data_type arr, data_type key)
覚えて： ここでのデータ型は、byte、char、double、int、float、short、long、さらには object などのプリミティブ データ型のいずれかにすることができます。
パラメーター：
- 検索する配列
- 検索する値
戻り値の型: 検索キーが配列に含まれている場合は、そのインデックス。それ以外の場合は (-(挿入ポイント) – 1)。挿入ポイントは、キーが配列に挿入されるポイントとして定義されます。キーより大きい最初の要素のインデックス、または配列内のすべての要素が指定されたキーより小さい場合は a.length です。これにより、キーが見つかった場合に限り、戻り値が 0 以上になることが保証されることに注意してください。
以下に留意すべき重要な点があります。
- 入力リストがソートされていない場合、結果は不定になります。
- 重複がある場合、どれが見つかるかは保証されません。
上で説明したように、このアルゴリズムは次のいずれかで操作できることをすでに説明しました。 Arrays.binarysearch() と比較 Collections.binarysearch() 。 Arrays.binarysearch() は、プリミティブ データ型の配列でも機能します。 コレクション .binarysearch() はオブジェクトのコレクションに対して機能します。 配列リスト そして リンクリスト 。
例 1:
ジャワ
// Java program to demonstrate working of Arrays.> // binarySearch() in a sorted array> // Importing Arrays class from> // java.util package> import> java.util.Arrays;> // Main class> public> class> GFG {> > // Main driver method> > public> static> void> main(String[] args)> > {> > // Declaring and initializing byte arrays> > // to search over them> > byte> byteArr[] = {> 10> ,> 20> ,> 15> ,> 22> ,> 35> };> > char> charArr[] = {> 'g'> ,> 'p'> ,> 'q'> ,> 'c'> ,> 'i'> };> > int> intArr[] = {> 10> ,> 20> ,> 15> ,> 22> ,> 35> };> > double> doubleArr[] = {> 10.2> ,> 15.1> ,> 2.2> ,> 3.5> };> > float> floatArr[] = {> 10> .2f,> 15> .1f,> 2> .2f,> 3> .5f };> > short> shortArr[] = {> 10> ,> 20> ,> 15> ,> 22> ,> 35> };> > // Using sort() method of Arrays class> > // and passing arrays to be sorted as in arguments> > Arrays.sort(byteArr);> > Arrays.sort(charArr);> > Arrays.sort(intArr);> > Arrays.sort(doubleArr);> > Arrays.sort(floatArr);> > Arrays.sort(shortArr);> > // Primitive datatypes> > byte> byteKey => 35> ;> > char> charKey => 'g'> ;> > int> intKey => 22> ;> > double> doubleKey => 1.5> ;> > float> floatKey => 35> ;> > short> shortKey => 5> ;> > // Now in sorted array we will fetch and> > // return elements/indiciesaccessing indexes to show> > // array is really sorted> > // Print commands where we are implementing> > System.out.println(> > byteKey +> ' found at index = '> > + Arrays.binarySearch(byteArr, byteKey));> > System.out.println(> > charKey +> ' found at index = '> > + Arrays.binarySearch(charArr, charKey));> > System.out.println(> > intKey +> ' found at index = '> > + Arrays.binarySearch(intArr, intKey));> > System.out.println(> > doubleKey +> ' found at index = '> > + Arrays.binarySearch(doubleArr, doubleKey));> > System.out.println(> > floatKey +> ' found at index = '> > + Arrays.binarySearch(floatArr, floatKey));> > System.out.println(> > shortKey +> ' found at index = '> > + Arrays.binarySearch(shortArr, shortKey));> > }> }> |
出力
35 found at index = 4 g found at index = 1 22 found at index = 3 1.5 found at index = -1 35.0 found at index = -5 5 found at index = -1
複雑さの分析:
時間計算量:
Arrays.binarySearch() メソッドの時間計算量は O(log n) です。ここで、n は入力配列の長さです。これは、このメソッドが二分探索アルゴリズムを使用して、ソートされた配列内のターゲット要素を見つけるためです。
補助スペース:
Arrays.binarySearch() メソッドで使用される補助スペースは、検索操作を実行するために入力配列以外の余分なスペースを必要としないため、O(1) です。
このメソッドには、検索する配列の範囲を指定できるバリアントもあります。これについては、オブジェクト配列の検索と同様に、今後の投稿で説明します。
例 2:
ジャワ
// Java Program to Illustrate 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 empty List> > List al => new> ArrayList();> > // Adding elements to the List> > al.add(> 12> );> > al.add(> 53> );> > al.add(> 23> );> > al.add(> 46> );> > al.add(> 54> );> > // Using binarySearch() method of Collections class> > // over random inserted element and storing the> > // index> > int> index = Collections.binarySearch(al,> 23> );> > // Print and display the index> > System.out.print(index);> > }> }> |
出力
2
複雑さの分析:
時間計算量:
Collections クラスの binarySearch() メソッドの時間計算量は O(log n) です。ここで、n はリスト内の要素の数です。
補助スペース:
Collections クラスの binarySearch() メソッドは追加のスペースを必要としないため、補助スペースの複雑さは O(1) になります。
