二分探索パターン

概要

二分探索は、ソート済みの配列から特定の要素を効率的に検索するアルゴリズムです。各ステップで探索範囲を半分に絞り込むことで、線形探索（O(n)）よりもはるかに高速に（O(log n)）目的の要素を見つけることができます。「分割統治法」の一種で、問題を小さな部分問題に分割して解決するアプローチです。

コードテンプレート

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // オーバーフロー防止
        
        if (nums[mid] == target) {
            return mid; // 要素が見つかった
        } else if (nums[mid] < target) {
            left = mid + 1; // 右半分を探索
        } else {
            right = mid - 1; // 左半分を探索
        }
    }
    
    return -1; // 要素が見つからなかった
}

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

このパターンを使用する問題例

• 1

  二分探索（Binary Search）: ソート済み配列から特定の値を検索する

• 2

  最初と最後の位置を検索（Find First and Last Position）: ソート済み配列で特定の値が最初と最後に現れる位置を見つける

• 3

  回転されたソート配列での検索（Search in Rotated Sorted Array）: 回転されたソート配列から特定の値を検索する

• 4

  平方根の計算（Sqrt(x)）: 整数の平方根を計算する（小数点以下切り捨て）

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

関連するパターン