Javaで二分探索を実装するにはどうすればよいですか?

Java で二分検索を行うには 2 つの方法があります。

1.Arrays.binarysearch()プリミティブ データ型にもなる配列に適用されます。

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

出力:

22 found at index = 3
40 Not found

2.Collections.binarysearch()ArrayList や LinkedList などのオブジェクト コレクションに適用されます。

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

出力:

10 found at index = 3
15 Not found

入力がソートされていない場合はどうなりますか?
入力リストがソートされていない場合、結果は未定義です。

重複がある場合はどうすればよいですか?
重複がある場合、どれが見つかるかは保証されません。

Collections.binarySearch は LinkedList に対してどのように機能しますか?
このメソッドは log(n) 時間で実行され、ArrayList などの「ランダム アクセス」リストに使用されます。指定されたリストが RandomAccess インターフェイスを実装しておらず、大きい場合、このメソッドは O(n) リンク トラバーサルと O(log n) 要素比較を実行する反復子ベースのバイナリ検索を実行します。

2 つの関数によって返される負の値の意味は何ですか?
この関数は、検索キーのインデックス (配列に含まれている場合) を返し、それ以外の場合は (-(挿入ポイント)-1) を返します。挿入ポイントは、キーが配列に挿入されるポイントとして定義されます。最初の要素のインデックスはキーより大きいか、配列内のすべての要素が指定されたキーより小さい場合は a.length です。これにより、キーが見つかった場合に限り、戻り値 >= 0 が保証されることに注意してください。

Java で独自の二分検索を実装するにはどうすればよいですか?

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    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); 
    } 
}

出力:

Element found at index 3

関連する推奨事項: "Java チュートリアル"

この記事は、バイナリ検索の実装方法の紹介です。 Java で、困っている友達に役立つことを願っています。

以上がJavaで二分探索を実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。