C言語での二分探索アルゴリズムの実装方法は何ですか？

2年 ago
海斗, 葵
1 minute

折半探索は二分探索とも呼ばれ、検索する配列が整列されている必要があります。

折り返し検索アルゴリズムを実装するには、次の手順に従います：

  1. パラメータとしてソートされた配列と検索対象の要素を受け取る関数を定義します。
  2. 配列の開始位置を指すポインターと、配列の終了位置を指すポインターを初期化する。
  3. ループを使用して、開始位置が終了位置以下かどうかを確認します。
  4. ループの中で、中間の位置のインデックスは、開始位置と終了位置の合計の半分に計算されます。
  5. 中央の要素が目標要素と等しい場合、中央の位置のインデックスを返す。
  6. 中央の要素が目標の要素よりも大きい場合は、終了位置のポインタを中央位置の前の要素に移動させます。
  7. 中央の要素が目標の要素よりも小さい場合、始点のポインタを中央の後ろの要素に移動させます。
  8. もしループが終了した際に目標要素が見つからない場合、-1を返して検索失敗を示す。

以下はサンプルコードです。

#include <stdio.h>

int binarySearch(int arr[], int target, int start, int end) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target = 12;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, target, 0, n - 1);
    
    if (result == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    
    return 0;
}

配列内の組織されたコードを検索し、目標となる要素12のインデックスを出力します。要素が配列内に存在する場合、対応するインデックスを出力します。存在しない場合は、「要素が見つかりません」と出力します。

bannerAds