線形探索(Linear Search)

2019年11月21日探索入門

線形探索とは

線形探索とは、入力を数値\(n\)とした時に、それがあるリストや配列に入っているかどうかを判定するためのアルゴリズムです。

1つのループ文を使うことでプログラムすることができます。

アルゴリズム

  1. \(i\) を0とする
  2. リストの \(i\) 番目に \(n\) が含まれているか確認する。含まれていれば「含まれていた」として \(i\) を出力して終了する
  3. \(i\) を１つ増やす
  4. \(i\) がリストの長さより小さければ 2. へ戻る。そうでなければ -1 を出力して終了する

簡単にまとめると、前から順番に配列を確認して行くだけの簡単なアルゴリズムです。

計算量

最悪の時(worst case)では、配列に探索する要素が含まれていないときで \(\Theta (n)\)

最善の時(best case)では、配列の先頭に探索したい要素が含まれている時で \(\Theta (1)\)

平均の時(average case)では、\(\Theta (n)\) となります。

プログラム例

\(3, 4, 0,2 \)が入っている配列から、\(0\)と\(5\)を線形探索するプログラムの例です。

Pythonの例 (Colaboratory などで確認してみて下さい）

def linear_search(arr, n):
  arr_len = len(arr)
  for i in range(arr_len):
    if arr[i]==n:
      return i
  return -1

arr = [3,4,0,2]
n = 0

print(linear_search(arr, 0)) # 出力は2
print(linear_search(arr, 5)) # 出力は-1

C++の例

#include<bits/stdc++.h>
using namespace std;

int linear_search(int arr[], int arr_len, int n){
    for(int i=0; i<arr_len; i++){
        if(arr[i] == n){
            return i;
        }
    }
    return -1;
}

int main(){
    int arr[] = {3,4,0,2};
    int arr_len = sizeof(arr)/sizeof(arr[0]); //配列の長さ
    cout << linear_search(arr, arr_len, 0) << "\n"; // 出力は2
    cout << linear_search(arr, arr_len, 5) << "\n"; // 出力は-1
    return 0;
}

探索入門