Help us understand the problem. What is going on with this article?

リスト探索(C言語)

More than 1 year has passed since last update.

探索とは

データ列の中に要素$x$があるか探すこと
特に、リスト探索はデータ列(リスト)から何らかのキーを持つ要素を見つけることが目的

線形探索

線形探索とは

リストの各要素を見て、要素$x$があるか探す。

サンプルコード

liner_sort.c
#include<stdio.h>

/* 線形探索(ソートされていなくても使える)*/
int liner_search (int list[], int list_size, int x) {
  int i = 0;
  while (i < list_size) {
    if (list[i] == x) { return i; }
    i++;
  }
  return -1;
}

/* 線形探索(ソート済みの時使える)*/
int sorted_liner_search (int list[], int list_size, int x) {
  int i = 0;
  while (i < list_size) {
    if (list[i] == x) { return i; }
    if (list[i] > x) { break; }  // これ以降にxがある可能性はないので打ち切り
    i++;
  }
  return -1;
}

int main (void) {
  int list[10] = {0, 4, 9, 10, 13, 17, 25, 36, 37, 40};
  int x;
  int answer;

  printf("x?> ");
  scanf("%d", &x);
  answer = liner_search(list, 10, x);
  if (answer != -1) { printf("%d\n", answer); }
  else              { printf("not exsist\n"); }

  printf("x?> ");
  scanf("%d", &x);
  answer = sorted_liner_search(list, 10, x);
  if (answer != -1) { printf("%d\n", answer); }
  else              { printf("Not exsist\n"); }
}

実行結果

x?> 5
not exsist
x?> 4
1

サンプルではlistはソート済みの配列なので、sorted_liner_search()もつかえる。

性能

  • 時間計算量$O(n)$
  • 比較回数
    • 探索不成功:$N+1$回
    • 探索成功:平均$N/2$回
  • 整列済みの場合、sorted_liner_search()を用いると、探索が不成功の時でも平均$N/2$回の比較で済む

二分探索

二分探索とは

整列済みのデータを二分し、要素$x$がある可能性のある部分データをまた二分し、という操作を繰り返す
例えば、整数が並んでいるデータ列の中から10を見つける場合、データ列の真ん中が5だったら後半を探し、データ列の真ん中が20だったら前半を探し$\cdots$という感じ

サンプルコード

binary_search.c
#include<stdio.h>

/* 二分探索 */
int binary_search (int list[], int list_size, int x) {
  int left, right, mid;
  left = 0;
  right = list_size - 1;

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

int main (void) {
  int list[10] = {0, 4, 9, 10, 13, 17, 25, 36, 37, 40};
  int x;
  int answer;

  printf("x?> ");
  scanf("%d", &x);
  answer = binary_search(list, 10, x);
  if (answer != -1) { printf("%d\n", answer); }
  else              { printf("not exsist\n"); }

}

実行結果

$ ./binary_search
x?> 9
2
$ ./binary_search
x?> 78
not exsist

性能

  • 時間計算量$O(\log_2n)$
  • 比較回数$\log_2(n+1)$以下
  • 比較回数の上限$C_n=C_{n/2}+1$

内挿探索

内挿探索とは

データが整列済みで一様に分布しているとすると、単純に「真ん中」よりも内挿した位置を見るほうが効率がいい
電話帳で「阿部さん」を探す時は、真ん中ではなく、先頭の方を見るのとおんなじ

データが一様に分布しているとすると、データ列の番号(配列の添え字)とデータの値(配列の中身)は大体比例するので、区間$[l,m]$と$[m,r]$の比を考えて、$a[m]\fallingdotseq x$となる$m$を選ぶ。

qiita-search-1.png

サンプルコード

注意:次のコードはxの値がlist[0]とlist[10]の範囲に入っていることが前提
interpolation_search.c
#include<stdio.h>

/* 内挿探索 */
int interpolation_search (int list[], int list_size, int x) {
  int left, right, mid;
  left = 0;
  right = list_size - 1;

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

int main (void) {
  int list[10] = {0, 4, 9, 10, 13, 17, 25, 36, 37, 40};
  int x;
  int answer;

  printf("x?> ");
  scanf("%d", &x);
  answer = interpolation_search(list, 10, x);
  if (answer != -1) { printf("%d\n", answer); }
  else              { printf("not exsist\n"); }

}

実行結果

$ a.exe
x?> 5
not exsist
$ a.exe
x?> 25
6

性能

データが一様分布なら理論上は二分探索よりも高速だが、$m$を求める計算コストが高いので、実際には要素数$n$がかなり大きくない限り二分探索より遅くなることが多い。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした