선형 검색 (보초법)

선형 검색

임의의 배열에서 원하는 데이터를 찾는 알고리즘

'임의의'인 이유는 크기 순서대로 정렬된 배열이라면 '이진 검색'을 사용하는 것이 낫다.

순서 무작위. 배열의 앞에서부터 데이터를 확인한다. 계산 시간은 O(n)

 

예) 지정한 값과 배열의 값이 같을 경우 종료. 배열에 같은 값이 중복으로 있을 경우에도, 처음 발견된 시점에 종료한다.

x=68인 경우, '1'

 

원하는 값이 발견되지 않은 경우 '-1'을 표시한다. -1은 인덱스로 사용할 수 없는 값이기 때문

#include <stdio.h>
#define LENGTH 10

int main(void) {
	int x = 0;
	int pos = -1;
	int a[] = { 72, 68, 92, 88, 41, 53, 97, 84, 39, 55 };

	printf("입력할 숫자 : ");
	scanf_s("%d", &x);
	printf("반복 실행 전 : x = %d, pos = %d\n", x, pos);

	// 배열을 끝까지 확인하지 않았고, 원하는 값이 발견되지 않았다면 반복하라는 의미
	for (int i = 0; i < LENGTH && pos == -1; ++i) {
		if (a[i] == x) {
			pos = i;
		}

		printf("반복 실행 중 : i = %d, pos = %d\n", i, pos);
	}

	printf("%d\n", pos);
	printf("반복 실행 후 :  pos = %d\n", pos);
	return 0;
}

 

선형 검색을 효율화하는 보초법의 값은?

선형 검색을 효율화하는 기술로써 보초병의 개념을 이용하는 '보초법'이 있다. = 대상 데이터

선형 검색은 배열의 끝에 보초법의 값에 해당하는 데이터를 추가한 후 검색 횟수를 줄여 값을 빠르게 찾을 수 있다. 

cf. 보초법의 값이 없을 때는요소 하나에 대해 두 가지 검사가 이루어진다.

 

예) 배열에서 53을 찾으려면 보초법의 값을 무엇으로 하면 좋을까?

배열에서 53이라는 값을 찾을 경우, 보초법의 값을 53으로 한다. 보초법의 값이 없을 때는 요소 하나에 대해 '53인가?'와 '끝인가?'라는두 가지 사항을 확인한다. 보초법을 사용하면 '끝인가?'라는 확인이 불필요해진다. 왜냐하면 배열의 중간에 53이 없더라도 끝에 53이 존재하기 때문

원하는 값이 나오면 바로 실행 중지

 

배열의 최솟값과 최댓값 구하기

#include <stdio.h>
#define LENGTH 10

int main(void) {
	int a[] = { 72, 68, 92, 88, 41, 53, 97, 84, 39, 55 };
	int max, min;

	max = a[0];
	min = a[0];

	for (int i = 0; i < LENGTH; ++i) {
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
	}

	printf("최댓값 : %d\n", max);
	printf("최솟값 : %d\n", min);
	return 0;
}