Cにおける線形検索アルゴリズムと実装

2年 ago
蓮, 翼
2 minutes

線形探索は基本的には順次検索アルゴリズムです。

このアルゴリズムでは、与えられた入力配列でキーエレメントが順番に検索されます。

もし入力配列の中にキーエレメントが見つかれば、その要素を返します。

リニアサーチアルゴリズム

リニアサーチ（配列X、値i）

  • Set j to 1
  • If j > n, jump to step 7
  • If X[j] == i, jump to step 6
  • Then, increment j by 1 i.e. j = j+1
  • Go back to step 2
  • Display the element i which is found at particular index i, then jump to step 8
  • Display element not found in the set of input elements.
  • Exit/End

線形探索のための疑似コード

procedure LINEAR_SEARCH (array, key)

   for each item in the array
      if match element == key
         return element's index
      end if
   end for

end procedure

C言語における線形探索の実装

  • Initially, we need to mention or accept the element to be searched from the user.
  • Then, we create a for loop and start searching for the element in a sequential fashion.
  • As soon as the compiler encounters a match i.e. array[element] == key value, return the element along with its position in the array.
  • If no values are found that match the input, it returns -1.
Linear Search
#include <stdio.h> 

int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 


int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
    else
    printf("Item is present at index %d", res);
    
	return 0; 
}

出力:

Item is present at index 5

線形探索の時間計算量

ループの最初の反復で要素が見つかる場合、ベストケースの計算量はO(1)です。

もし配列の要素がn個で、検索したい要素が配列の最後にある場合、最悪の場合の時間計算量はO(n)です。

結論

したがって、この記事では、私たちは線形検索アルゴリズムを理解し実装しました。

bannerAds