アルゴリズムとデータ構造：リニアサーチ

リニアサーチは配列の先頭から順番に調べて行って探している数字と同じであればキーを返す。
単純挿入ソートで使った方法。逐次探索、線形探索とも言う。C++標準ライブラリのfind()が相当する。

[計算量]
O(N)

[linear_search.c]

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

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

int linear_search(int x, int *a, int num) ;

int linear_search(int x, int *a, int num) {
    int n = 0;

    while (n < num && a[n] != x) {
        ++n; 
    }
    if (n < num){
        return n; 
    }

    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]  = rand() % 10;
        printf("[%d]:%d",i,array[i]);
    }

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

    r = linear_search(i, array, N);

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

    return EXIT_SUCCESS;
}

改良版。whileの条件が1つ減った。このやり方は覚えておいたらいいかも。10%くらい速くなるそうです。
[linear_search_plus.c]

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

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

int linear_search(int x, int *a, int num) ;

int linear_search(int x, int *a, int num) {
    int n = 0, t;

    t = a[num - 1];
    a[num - 1] = x;
    while (a[n] != x) {
        ++n; 
    }

    a[num - 1] = t;
    if (n < num - 1){
        return n; 
    }
    if (x == t){
        return n; 
    }

    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]  = rand() % 10;
        printf("[%d]:%d",i,array[i]);
    }

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

    r = linear_search(i, array, N);

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

    return EXIT_SUCCESS;
}