前回まではソートアルゴリズムについて記載していましたが、今回は探索アルゴリズムの二分探索についてです
-
-
マージソートを理解する - ナストンのまとめ
前回に引き続き今回はマージソートについてです マージソートって？ クイックソートと同じく処理が速いものとなりますが、ソー ...
続きを読む
二分探索って？
ソート済みのデータ構造において、中央の要素と目標の要素を比較して探索範囲を半分に絞りながら進むアルゴリズムとなります。詳しくは以下のサイトが参考になるかと思います
-
-
二分探索とは - ITを分かりやすく解説
二分探索（にぶんたんさく）とは、探索のアルゴリズムの1つです。本記事では、探索対象の配列やリストを「昇順」または「降順」 ...
続きを読む
二分探索を実装する
実装内容としては難しくなく、対象の値が配列の左にあるのか右にあるのかを判定を繰り返し、対象を見つけるといったものです
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;
}
問題なく対象の値を探し出すことができました
会社紹介
私が所属しているアドバンスド・ソリューション株式会社(以下、ADS)は一緒に働く仲間を募集しています
会社概要
「技術」×「知恵」＝顧客課題の解決・新しい価値の創造
この方程式の実現はADSが大切にしている考えで、技術を磨き続けるgeekさと、顧客を思うloveがあってこそ実現できる世界観だと思っています
この『love & geek』の精神さえあれば、得意不得意はno problem！
技術はピカイチだけど顧客折衝はちょっと苦手。OKです。技術はまだ未熟だけど顧客と知恵を出し合って要件定義するのは大好き。OKです
凸凹な社員の集まり、色んなカラーや柄の個性が集まっているからこそ、常に新しいソリューションが生まれています
ミッション
私たちは、テクノロジーを活用し、業務や事業の生産性向上と企業進化を支援します
-
-
アドバンスド・ソリューション株式会社
アドバンスド・ソリューションは主にMicrosoft製品を使用して、企業の生産性向上に取り組んでいます。要件定義から導入 ...
サイトへ移動
-
-
お問い合わせ | アドバンスド・ソリューション株式会社
お問い合わせはこちら
