二分探索を理解する

前回まではソートアルゴリズムについて記載していましたが、今回は探索アルゴリズムの二分探索についてです

二分探索って？

ソート済みのデータ構造において、中央の要素と目標の要素を比較して探索範囲を半分に絞りながら進むアルゴリズムとなります。詳しくは以下のサイトが参考になるかと思います

二分探索を実装する

実装内容としては難しくなく、対象の値が配列の左にあるのか右にあるのかを判定を繰り返し、対象を見つけるといったものです

template <typename T>
int binarySearch(const std::vector<T>& arr, T target) {
    int left = 0;
    int right = arr.size() - 1;

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

        // 中央の要素が目標と一致する場合
        if (arr[middle] == target) {
            return middle;
        }

        // 中央の要素よりも小さい場合、右側を探索
        if (arr[middle] > target) {
            right = middle - 1;
        }
        // 中央の要素よりも大きい場合、左側を探索
        else {
            left = middle + 1;
        }
    }

    // 要素が見つからなかった場合
    return -1;
}

実際に動かしてみる

ソート済み配列であることが前提条件となるので、前回までのいずれかのソートアルゴリズムを使用してソートしたものに実際に使ってみます

std::set<int> uniqueNumbers; // 重複を防ぐためにstd::setを使用
std::vector<int> arr;

// 乱数生成器の初期化
std::random_device rd;
std::mt19937 gen(rd());

// 1から100までのランダムな数字を生成
std::uniform_int_distribution<int> distribution(1, 100);

while (uniqueNumbers.size() < 10) {
    int randomNumber = distribution(gen);

    // 重複を防ぐために挿入前に確認
    if (uniqueNumbers.find(randomNumber) == uniqueNumbers.end()) {
        uniqueNumbers.insert(randomNumber);
        arr.push_back(randomNumber);
    }
}

// ソートする
QuickSort::quickSort(arr, 0, arr.size() - 1);

std::cout << "Original Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

std::uniform_int_distribution<int> targetDis(0, arr.size() - 1);
int randomNumber = targetDis(gen);

int target = arr[randomNumber];

// 二分探索を実行
int result = binarySearch(arr, target);

// 結果を表示
if (result != -1) {
    std::cout << "Element " << target << " found at index " << result << std::endl;
}
else {
    std::cout << "Element " << target << " not found in the array." << std::endl;
}

問題なく対象の値を探し出すことができました