二分探索(バイナリサーチ)のアルゴリズム

このレッスンでは、Objective-Cで二分探索(バイナリサーチ)のアルゴリズムを実装する方法を学び、効率よく値を探す考え方を理解することを目標にします。「Objective-C 二分探索実装」で調べている方向けです。

二分探索は、並び替え済みのデータから目的の値を効率よく探すアルゴリズムです。「辞書を開くとき、真ん中あたりから探して範囲を半分に絞っていく」ようなイメージです。

サンプルコードでは、lowとhighという2つの位置から範囲の中央midを計算し、目的の値と比較しながらlowかhighを更新して範囲を絞り込んでいます。[arr[mid] integerValue]でNSNumberから整数値を取り出している点にも注目してみましょう。

初心者がよくつまずくのが、二分探索を使うには配列が事前に並び替えられている必要がある点です。探索対象のデータがすでに並び替えられていることが前提条件なので、事前のソートを忘れないようにしましょう。

実際の開発現場では、大量のデータの中から特定の値を高速に探したい場面で、二分探索の考え方が広く応用されています。

📖 お手本コード

NSInteger binarySearch(NSArray *arr, NSInteger target) {
    NSInteger low = 0, high = arr.count - 1;
    while (low <= high) {
        NSInteger mid = (low + high) / 2;
        NSInteger val = [arr[mid] integerValue];
        if (val == target) return mid;
        if (val < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

NSArray *nums = @[@1, @3, @5, @7, @9, @11];
NSLog(@"%ld", (long)binarySearch(nums, 7));
NSLog(@"%ld", (long)binarySearch(nums, 4));

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではObjective-Cを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
大量のデータの中から目的の値を高速に見つけ出せるようになります。