アルゴリズムとデータ構造まとめその2 サーチ

はじめに

この記事は著者が学習書の内容を備忘録としてまとめたものです。
前
次
第二回の今回はサーチについてまとめます。

サーチ概要

サーチとはデータの中から、ある値と一致する値を持つものを探すことであり、主な手法は以下の2つである。

リニアサーチ

概要

最もシンプルな手法で、データを先頭から一つずつ確認していく。O(N)。 　 実際には、次回の記事で説明する自己組織化探索にする。

コード

int linear_search(int x, int *a, int num){
  int n = 0, t;
  // 番人
  t = a[num - 1];
  a[num - 1] = x;
  while(n < num && a[n] != x){
    n++;
  }

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

  return NOT_FOUND;
}

バイナリサーチ

概要

クイックソートの逆バージョンのようなサーチ法。既にソートされているデータに対して、二分探索を繰り返してサーチを行う。O(logN)。

コード

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;
}