C・C++の二分探索
このレッスンでは、Cの自作ループとC++のstd::lower_boundで、並べ替え済みの配列をO(log n)の時間で探索します。
はじめに
二分探索は、探す値を探索範囲の真ん中の要素と比べ、その値が入っているはずのない半分を候補から外します。これを繰り返すと探索範囲はとても速く狭まりますが、入力データはあらかじめ並べ替えられていなければなりません。
大切なポイント
- 空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
- まず正しく動かし、最適化はその後にしましょう。
- 実際のコードでは、標準ライブラリの既製の関数を優先しましょう。
C・C++の二分探索のビジュアライザー
O(log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
CとC++のコード例
C
main.c
#include <stdio.h>
int search(const int *values, int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
int main(void) {
int values[] = {3, 7, 11, 16, 23, 28};
printf("index=%d\n", search(values, 6, 23));
}
index=4C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{3, 7, 11, 16, 23, 28};
auto match = std::lower_bound(values.begin(), values.end(), 23);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=4CとC++の比較
Cのバージョンでは、インデックスがとても大きいときのオーバーフローを避けるため、真ん中の位置を(low + high) / 2ではなくlow + (high - low) / 2で計算します。比較のたびに、lowかhighが残りの半分へ移ります。C++のバージョンはstd::lower_boundを使い、探す値より小さくない最初の位置を見つけます。どちらも計算量はO(log n)です。
C
ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。
C++
イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 比較を1回ずつ紙の上でたどってみましょう。
- 重複した値や、とても大きい値・小さい値で試しましょう。
- 自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ