アルゴリズムとデータ構造：バイナリサーチ

ニ分探索。
配列の真ん中の値と探している値を比較、それを繰り返すことでターゲットを絞って行く。
対象となる配列がソートされている必要がある。
データ量が少なかったり、ソートする時間がない場合はリニアサーチにしましょう。

[計算量]
O(log N)

[binary_seach.c]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NOT_FOUND (-1)
#define N (10)

int binary_search(int x, int *a, int left, int right) ;

int binary_search(int x, int *a, int left, int right) {
    int mid = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        if (a[mid] == x) {
            return mid; 
        }
        printf("a[mid]:%d < x:%d=>%d\n", a[mid] ,x ,a[mid] < x);
        if (a[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = array[i-1] + rand() % 3;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = binary_search(i, array, 0, N - 1);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}

改良版。配列内に同じ値が存在する場合、真ん中に近いものしか取得できないのを左よせで検索。ちょっとコード変えると右よせでも検索できる。
[binary_seach_plus.c]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NOT_FOUND (-1)
#define N (10)

int binary_search(int x, int *a, int left, int right) ;

int binary_search(int x, int *a, int left, int right) {
    int mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (a[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid; 
        }
    }
    if (a[left] == x) {
        return left; 
    }

    return NOT_FOUND;
}

int main(void){
    int i,r,array[N];
    
    srand((unsigned int) time(NULL));
    printf("array...\n");
    for(i = 0; i <  N; i++){
        array[i]  = array[i - 1] + rand() % 3;
        printf("[%d]:%d",i,array[i]);
    }

    printf("\n何をさがしますか:");
    scanf("%d", &i);

    r = binary_search(i, array, 0, N - 1);

    if (r == NOT_FOUND) {
        printf("%dはみつかりませんでした\n", i); 
    }
    else {
        printf("%dは%d番目です\n", i, r); 
    }

    return EXIT_SUCCESS;
}

C言語にはbsearch()、C++にはbinary_seach()という関数でバイナリーサーチができる。