C에서의 선형 검색 알고리즘 및 구현

선형 검색은 기본적으로 순차 검색 알고리즘입니다.

이 알고리즘에서 키 요소는 주어진 입력 배열에서 순차적으로 검색됩니다.

키 요소가 입력 배열에서 발견되면 요소를 반환합니다.

선형 검색 알고리즘

Linear_Search(배열 X, 값 i)

• j를 1로 설정
• j > n인 경우 7단계로 이동
• X[j] == i인 경우 6단계로 이동
• 그런 다음 j를 1씩 증가시킵니다. 즉, j=j+1
• 2단계로 돌아가기
• 특정 인덱스 i에서 찾은 요소 i를 표시한 다음 8단계로 이동합니다.
• 입력 요소 집합에서 요소를 찾을 수 없습니다.
• 종료/종료

선형 검색을 위한 의사 코드

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에서 선형 검색 구현

• 처음에는 사용자로부터 검색할 요소를 언급하거나 수락해야 합니다.
• 그런 다음 for 루프를 만들고 순차적으로 요소 검색을 시작합니다.
• 컴파일러가 일치 항목(예: array[element] == 키 값)을 만나자마자 배열에서 해당 위치와 함께 요소를 반환합니다.
• 입력과 일치하는 값이 없으면 -1을 반환합니다.

#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)입니다.

결론

따라서 이 기사에서는 선형 검색 알고리즘을 이해하고 구현했습니다.