Java Academy · レッスン

Arrays.binarySearch

Q: 「Arrays.binarySearch」で何を学びますか？

ソート済み配列を検索します ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

ソート済み配列を検索します

「Arrays.binarySearch」はCoddyKit上の無料Java Academyレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

ソート済み配列を検索する

Arrays.binarySearchは、ソート済みの配列から要素をO(log n)時間で検索します。検索範囲を繰り返し半分にするため、すべての要素を調べるよりもはるかに高速です。

ソート済みという前提条件

配列は、あらかじめ昇順にソートされていなければなりません。ソートされていない場合、結果は未定義です。不確かな場合は、必ず先にArrays.sortを実行してください。

基本的な検索

値が見つかった場合、binarySearchはそのインデックスを返します。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int index = Arrays.binarySearch(nums, 8);
        System.out.println("Found at index " + index);
    }
}

値が見つからない場合

値が存在しない場合、戻り値は負の値になります。これは-(insertionPoint) - 1と等しくなります。挿入位置とは、配列のソート順を維持するためにその値を置く位置です。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int result = Arrays.binarySearch(nums, 5);
        System.out.println("Raw result: " + result);
    }
}

挿入位置を復元する

負の結果を挿入インデックスに変換するには、-(result) - 1を計算します。これにより、見つからなかった値を挿入する位置が分かります。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int result = Arrays.binarySearch(nums, 5);
        if (result < 0) {
            int insertionPoint = -(result) - 1;
            System.out.println("Would insert at index " + insertionPoint);
        }
    }
}

オブジェクト配列を検索する

binarySearchは、自然順序を使ってオブジェクト配列も検索できます。配列は、検索時の比較方法と同じ方法でソートされていなければなりません。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Dave"};
        int index = Arrays.binarySearch(names, "Charlie");
        System.out.println("Charlie at index " + index);
    }
}

Comparatorを使って検索する

配列を独自のComparatorでソートした場合は、binarySearchにも同じComparatorを渡す必要があります。そうしないと、結果に意味がありません。

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Dave", "Charlie", "Bob", "Alice"};
        Comparator<String> desc = Comparator.reverseOrder();
        Arrays.sort(names, desc);
        int index = Arrays.binarySearch(names, "Charlie", desc);
        System.out.println("Index: " + index);
    }
}

範囲を指定して検索する

binarySearch(array, fromIndex, toIndex, key)を使うと、配列の一部に検索範囲を限定できます。範囲の境界は、sortと同じ包含・排他的ルールに従います。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10, 12};
        int index = Arrays.binarySearch(nums, 1, 5, 8);
        System.out.println("Index: " + index);
    }
}

重複値の結果は保証されない

配列に重複する値が含まれている場合、どの一致するインデックスが返されるかは保証されません。二分探索は、一意なキーを持つ配列で使うのが最適です。

単純なループではいけない理由

線形探索はO(n)で、ソートされていないデータにも使えます。二分探索はO(log n)ですが、ソート済みのデータが必要です。大規模なデータセットを繰り返し検索する場合は、一度ソートして何度も二分探索することで大きな効果が得られます。

一連の処理にまとめる

ソートしてから検索し、結果を安全に解釈します。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] ids = {40, 10, 30, 20};
        Arrays.sort(ids);
        int r = Arrays.binarySearch(ids, 30);
        if (r >= 0) {
            System.out.println("Found 30 at index " + r);
        } else {
            System.out.println("Not found; insert at " + (-(r) - 1));
        }
    }
}

確認問題

binarySearchについての理解を確認しましょう。

まとめ

Arrays.binarySearchを使った高速な検索方法を学びました。

配列は先にソートしておく必要がある
0以上の結果は、見つかった要素のインデックスを表す
負の結果には、挿入位置が-(result) - 1としてエンコードされている
ソートと検索には同じComparatorを使う

よくある質問

「Arrays.binarySearch」レッスンは無料ですか？

はい。「Arrays.binarySearch」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「Arrays.binarySearch」で何を学びますか？

ソート済み配列を検索しますブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン2/4です。

「Arrays.binarySearch」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Java Academyに戻る