二分探索をCとC++で実行

二分探索とは？

比較ごとに残り範囲の半分を捨てます。

ソート済みデータを対数時間で探索します。

重要なポイント

空、1要素、重複、ソート済み入力をテストします。
正しさと最適化を分けます。
実務ではstandard libraryを優先します。

二分探索のビジュアライザー

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=4

C++

実行 →

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=4

CとC++の比較

入力はsorted必須です。C loopとstd::lower_boundはrandom-access rangeでO(log n)です。

C

loop、pointer、length、bufferを明示します。

C++

iteratorとalgorithmが操作と格納方法を分離します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

各比較を手で追跡します。
重複と極値をテストします。
standard libraryとbenchmarkします。