配列検索(C言語実装)

この文書には、主に一般的な配列検索方法が含まれています.
線形検索
線形検索は最も簡単で乱暴な検索方法で、検索する要素が見つかるまで配列の最初の要素から直接検索します.

#include 
#include 

int LineSearch(int *p,int length,int search)
{
    for(int i=0;i

にぶんたんさく
折半ルックアップとも呼ばれ、二分法を用いたルックアップ方法であるため、この方法を用いてルックアップする場合は、元の配列を先にソートする必要がある.

配列要素が昇順配列

であると仮定する.

コレクションの中間要素を検索する要素と比較し、等しい場合は

を返す.

中間要素が検索する要素より大きい場合、左半分で検索し、逆に右半分で

を検索する.

以上の操作

を繰り返す.
ループ実装

#include 
#include 

void SelectSort(int *p,int n)
{
    for(int i=0;ip[j])
            {
                p[i] = p[i]^p[j];
                p[j] = p[i]^p[j];
                p[i] = p[i]^p[j];
            }
}

int BinarySearch(int *p,int low,int high,int search)
{

    while(low <= high)
    {
        int mid = (low+high)/2;
        if(search == p[mid])
            return mid;
        else if(search < p[mid])
                high = mid-1;
            else
                low = mid+1;
    }
    return -1;
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    SelectSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d
",arr[i]);

    printf("%d
",BinarySearch(arr,0,9,9));

    return 0;
}

結果:

0
1
2
3
4
5
6
7
8
9
9

再帰的な実装

#include 
#include 

void SelectSort(int *p,int n)
{
    for(int i=0;ip[j])
            {
                p[i] = p[i]^p[j];
                p[j] = p[i]^p[j];
                p[i] = p[i]^p[j];
            }
}

int BinarySearch(int *p,int low,int high,int search)
{
    if(low <= high)
    {
        int mid = (low+high)/2;
        if(search == p[mid])
            return mid;
        else if(search < p[mid])
            BinarySearch(p,low,mid-1,search);
        else
            BinarySearch(p,mid+1,high,search);
    }
    else
        return -1;
}

int main(void)
{
    int arr[10] = {1,5,9,6,4,3,2,7,8,0};

    SelectSort(arr,10);

    for(int i=0;i<10;i++)
        printf("%d
",arr[i]);

    printf("%d
",BinarySearch(arr,0,9,9));

    return 0;
}

結果:

0
1
2
3
4
5
6
7
8
9
9