[C++] binary_search()の使い方 – ニ分探索

#include <iostream>
#include <algorithm> // binary_searchを使用するために必要
#include <vector>
int main() {
    // ソートされた整数のベクターを作成
    std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15};
    // 探索する値
    int target = 7;
    // binary_searchを使用して値が存在するか確認
    bool found = std::binary_search(numbers.begin(), numbers.end(), target);
    // 結果を出力
    if (found) {
        std::cout << "値 " << target << " は配列に存在します。" << std::endl;
    } else {
        std::cout << "値 " << target << " は配列に存在しません。" << std::endl;
    }
    return 0;
}

値 7 は配列に存在します。

#include <iostream>
#include <algorithm> // binary_searchを使用するために必要
#include <vector>
#include <string>
int main() {
    // ソートされた文字列のベクターを作成
    std::vector<std::string> names = {"Alice", "Bob", "Charlie", "David", "Eve"};
    // 探索する文字列
    std::string target = "Charlie";
    // binary_searchを使用して文字列が存在するか確認
    bool found = std::binary_search(names.begin(), names.end(), target);
    // 結果を出力
    if (found) {
        std::cout << "文字列 \"" << target << "\" は配列に存在します。" << std::endl;
    } else {
        std::cout << "文字列 \"" << target << "\" は配列に存在しません。" << std::endl;
    }
    return 0;
}

文字列 "Charlie" は配列に存在します。

#include <iostream>
#include <algorithm> // binary_searchを使用するために必要
#include <vector>
struct Person {
    std::string name;
    int age;
};
// 比較関数
bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name;
}
int main() {
    // ソートされたPersonのベクターを作成
    std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    // 探索する人物
    Person target = {"Bob", 0}; // 年齢は無視
    // binary_searchを使用して人物が存在するか確認
    bool found = std::binary_search(people.begin(), people.end(), target, compareByName);
    // 結果を出力
    if (found) {
        std::cout << "人物 \"" << target.name << "\" は配列に存在します。" << std::endl;
    } else {
        std::cout << "人物 \"" << target.name << "\" は配列に存在しません。" << std::endl;
    }
    return 0;
}

人物 "Bob" は配列に存在します。

#include <iostream>
#include <algorithm> // lower_boundを使用するために必要
#include <vector>
int main() {
    std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 10;
    // lower_boundを使用して指定した値以上の最初の要素の位置を取得
    auto it = std::lower_bound(numbers.begin(), numbers.end(), target);
    // 結果を出力
    if (it != numbers.end()) {
        std::cout << "値 " << target << " 以上の最初の要素は " << *it << " です。" << std::endl;
    } else {
        std::cout << "値 " << target << " 以上の要素は存在しません。" << std::endl;
    }
    return 0;
}

値 10 以上の最初の要素は 11 です。

#include <iostream>
#include <algorithm> // upper_boundを使用するために必要
#include <vector>
int main() {
    std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 10;
    // upper_boundを使用して指定した値より大きい最初の要素の位置を取得
    auto it = std::upper_bound(numbers.begin(), numbers.end(), target);
    // 結果を出力
    if (it != numbers.end()) {
        std::cout << "値 " << target << " より大きい最初の要素は " << *it << " です。" << std::endl;
    } else {
        std::cout << "値 " << target << " より大きい要素は存在しません。" << std::endl;
    }
    return 0;
}

値 10 より大きい最初の要素は 11 です。

#include <iostream>
#include <algorithm> // equal_rangeを使用するために必要
#include <vector>
int main() {
    std::vector<int> numbers = {1, 3, 5, 5, 5, 7, 9};
    int target = 5;
    // equal_rangeを使用して指定した値と等しい要素の範囲を取得
    auto range = std::equal_range(numbers.begin(), numbers.end(), target);
    // 結果を出力
    std::cout << "値 " << target << " は " << (range.second - range.first) << " 個存在します。" << std::endl;
    return 0;
}

値 5 は 3 個存在します。

#include <iostream>
#include <algorithm> // findを使用するために必要
#include <vector>
int main() {
    std::vector<int> numbers = {1, 3, 5, 7, 9};
    int target = 5;
    // findを使用して指定した値を持つ最初の要素の位置を取得
    auto it = std::find(numbers.begin(), numbers.end(), target);
    // 結果を出力
    if (it != numbers.end()) {
        std::cout << "値 " << target << " は配列に存在します。" << std::endl;
    } else {
        std::cout << "値 " << target << " は配列に存在しません。" << std::endl;
    }
    return 0;
}

値 5 は配列に存在します。

#include <iostream>
#include <algorithm> // binary_searchを使用するために必要
#include <vector>
int main() {
    // ソートされた整数の配列を作成
    std::vector<int> numbers = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    
    // 探索する値
    int target = 14;
    // binary_searchを使用して値が存在するか確認
    bool found = std::binary_search(numbers.begin(), numbers.end(), target);
    // 結果を出力
    if (found) {
        std::cout << "値 " << target << " は配列に存在します。" << std::endl;
    } else {
        std::cout << "値 " << target << " は配列に存在しません。" << std::endl;
    }
    return 0;
}

値 14 は配列に存在します。

#include <iostream>
#include <algorithm> // binary_searchを使用するために必要
#include <vector>
#include <string>
struct Student {
    std::string name;
    int score;
};
// 比較関数
bool compareByName(const Student& a, const Student& b) {
    return a.name < b.name;
}
int main() {
    // ソートされた学生のベクターを作成
    std::vector<Student> students = {{"Alice", 85}, {"Bob", 90}, {"Charlie", 78}, {"David", 92}};
    // 探索する学生
    Student target = {"Bob", 0}; // スコアは無視
    // binary_searchを使用して学生が存在するか確認
    bool found = std::binary_search(students.begin(), students.end(), target, compareByName);
    // 結果を出力
    if (found) {
        std::cout << "学生 \"" << target.name << "\" は配列に存在します。" << std::endl;
    } else {
        std::cout << "学生 \"" << target.name << "\" は配列に存在しません。" << std::endl;
    }
    return 0;
}

学生 "Bob" は配列に存在します。

#include <algorithm> // binary_searchを使用するために必要
#include <iostream>
#include <vector>
#include <string>

struct Product {
    std::string name;
    double price;
};

// 比較関数
bool compareByPrice(const Product& a, const Product& b) {
    return a.price < b.price;
}

int main() {
    // 商品のベクターを作成
    std::vector<Product> products = {
        {"Apple",  100.0},
        {"Banana", 80.0 },
        {"Cherry", 150.0},
        {"Date",   120.0}
    };

    // 価格でソート
    std::sort(products.begin(), products.end(), compareByPrice);

    // 探索する価格
    double targetPrice = 120.0;

    // binary_searchを使用して価格が存在するか確認
    auto it = std::lower_bound(products.begin(), products.end(), Product{"", targetPrice}, compareByPrice);

    // lower_boundで見つかった位置が範囲内であり、価格が一致するか確認
    if (it != products.end() && it->price == targetPrice) {
        std::cout << "価格 " << targetPrice << " の商品 " << it->name << " は存在します。" << std::endl;
    } else {
        std::cout << "価格 " << targetPrice << " の商品は存在しません。" << std::endl;
    }

    return 0;
}

価格 120 の商品 Date は存在します。