close

(Binary Search) C++ の 二分探索アルゴリズム- 説明、例、およびコード

二分検索アルゴリズムは、並べ替えられたリスト内の特定の要素を検索するより効率的な方法です。 要素を順番にチェックする線形検索とは異なり、二分検索ではリストを半分に分割し、ターゲット要素と中央の要素を比較します。 この処理は、目的の要素が見つかるか、検索範囲が空になるまで繰り返されます。

使い方

  1. ソートされたリスト全体から始めます。
  2. 現在の検索範囲の中央の要素を検索します。
  3. 中央の要素をターゲット値と比較します。
  4. 中央の要素がターゲット値と等しい場合、検索は成功します。
  5. 中央の要素がターゲットより大きい場合は、範囲の左半分を検索します。
  6. 中央の要素がターゲットより小さい場合は、範囲の右半分を検索します。
  7. 目的の要素が見つかるか、検索範囲が空になるまで手順 2 ～ 6 を繰り返します。

例

整数のソートされたリストを考えて、二分探索を使用して数値 34 を見つけたいとします。

ソートされたリスト: {12、23、34、45、56、67、89、90}

  1. リスト全体から始めます。
  2. 中間要素: 56(位置 4)。 34と比較してください。
  3. 56 は 34 より大きいです。左半分を検索します。
  4. 新しい中間要素: 23(位置 1)。 34と比較してください。
  5. 23 は 34 より小さいです。右半分を検索します。
  6. 新しい中間要素: 45(位置 3)。 34と比較してください。
  7. 45 は 34 より大きいです。左半分を検索します。
  8. 新しい中間要素: 34(位置 2)。 ターゲットが見つかりました。

C++ のコード例 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

この例では、この binarySearch 関数は、整数のソートされたリストから数値 34 を検索するために使用されます。 結果はリスト内の 34 の位置(位置は 0 から始まります)、または番号が見つからない場合は -1 になります。