【アルゴリズム】2分探索｜基本情報技術者科目B対策

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となる探索の問題について考えてみましょう。

探索アルゴリズムとは？？
2分探索とは？？
どんなときに使う？
2分探索の実装例（プログラム）
まとめ

探索アルゴリズムとは？？

配列のようなデータの集合から目的の値をを持った要素を探し出すアルゴリズムのことを言います。

何らかの項目（属性）に着目して探索を行います。このとき、着目する項目を「キー」と呼びます。例えば、年齢に着目して探索を行う場合、キーは年齢ということになります。

＜探索アルゴリズム例＞

・線形探索

・２分探索

・ハッシュ法　　等

2分探索とは？？

2分探索（Binary Search）は、データがソートされた配列（またはリスト）内に存在するかどうかを効率的に検索するアルゴリズムです。このアルゴリズムは、データを中央値と比較して範囲を狭めながら探索を進めます。

例えば、配列を探索する手順は下記のようになる。

1. ソートされた配列の中央の要素を取得します。
2. 中央の要素と目標値を比較します。
- もし中央の要素が目標値と一致すれば、探索終了です。
- もし中央の要素が目標値よりも小さければ、

　探索範囲を中央よりも右側に絞ります。
- もし中央の要素が目標値よりも大きければ、

探索範囲を中央よりも左側に絞ります。
3. 新しい探索範囲で1から2の手順を繰り返します。
4. 探索範囲が空になるまで上記の手順を続けます。

どんなときに使う？

2分探索は、要素数が大きいソート済み配列に対しても非常に効率的であり、一度の比較で探索範囲を半分に絞ることができます。

そのため、線形探索（要素を先頭から順番に比較していく方法）に比べて高速な検索が可能です。ただし、2分探索を行う前に配列をソートする必要があるため、事前のソート処理が必要です。

2分探索の実装例（プログラム）

実装例は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

＜実装例＞

import java.util.*;
import java.lang.*;

public class Main {
    static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // 目標値が見つかった場合、インデックスを返す
            }

            if (arr[mid] < target) {
                left = mid + 1; // 中央値よりも目標値が大きい場合、探索範囲を右側に絞る
            } else {
                right = mid - 1; // 中央値よりも目標値が小さい場合、探索範囲を左側に絞る
            }
        }

        return -1; // 目標値が見つからなかった場合、-1を返す
    }

    public static void main(String[] args) {
        int[] arr = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 2;

        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("目標値が見つかりませんでした");
        } else {
            System.out.println("目標値はインデックス " + result + " にあります");
        }
    }
}