3-2장 선형 검색

1. 선형 검색 다루기 

 

 - 배열에서의 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색 

 -ex) 배열 {6,4,3,2,1,2,8}에서의 검색 

 

  -2를 검색 : 검색 성공

 

 - 5를 검색 : 검색 실패 

 

 - 선형 검색에서 배열 검색의 종료 조건

 1) 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패)

  - i == n이 성립하는 경우 

 2) 검색할 값과 같은 요소를 발견한 경우 (검색 성공)

 - a[i] == key가 성립하는 경우 

 

 - 요소 개수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드 

nt i =0;
while(1) {
    if(i ==n) {
    	return -1; //검색 실패 
    if(a[i] =-key)
    	return 1; //검색 성공
    i++;
}

- 요소 개수가 n인 배열 a에서 값이 key인 요소를 검색 (while문)

//선형 검색
#include <stdio.h> 
#include <stdlib.h>

//요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색
int search(const int a[], int n, int key) 
{
	int i=0; 
	while(1) {
		if(i==n)
			return -1; //검색 실패
	 	if(a[i]==key) 
	 		return i; //검색 성 공
	 	i++; 
	}
}

int main()
{
	int nx,ky;
	puts("선형검색:");
	printf("요소 개수:");
	scanf("%d",&nx);
	
	int *x =(int*)calloc(nx,sizeof(int)); //요소의 개수가 nx인 배열 x 생성 
	for(int i=0; i <nx; i++) {
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	printf("검색값:");
	scanf("%d",&ky);
	int idx = search(x,nx,ky); //배열 x의 값이 ky인 요소를 선형 검색
	if(idx == -1)
		printf("검색에 실패했습니다.");
	else 
	 	printf("%d는x[%d]에 있습니다.\n",ky,idx);
 	free(x);
	 
	return 0; 
}

 

 - 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색 (for문)

int serach(const int a[], int n, int key)
{
    for(int i=0; i<n; i++)
    	if(a[i]==key)	
        	return i; //검색 성공
    return -1; 검색 실패 
}

 

2. 보초법(sentinel)으로 검색 다루기 

 

- 선형 검색은 반복할때 마다 종료조건 1,2를 모두 체크 

- 보초법은 종료조건 1번 사용

 - 배열 요소 a[0]~a[6]은 원래 데이터 

 - 맨 끝 요소 a[7]은 검색하기 전에 준비하는 보초(sentinel)

  -> 검색하고자 하는 키값과 같은 값을 저장 

 

 - 원하는 값이 원래 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 a[i]==key가 성립

  -> 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할

 

- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형검색 (보초법)

//선형 검색(보초법) 
#include <stdio.h> 
#include <stdlib.h>

//요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법)
int serach(int a[], int n, int key) 
{
	int i=0;
	a[n]=key; //맨끝에 보초 추가 
	while(1) {
		if(a[i] == key)
			break; //원하는 키값을 찾은 경우 
		i++; 
	}
	return i == n?-1: i; 
}

int main()
{
	int nx, ky;
	
	puts("선형검색(보초법)");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x =(int *) calloc(nx+1, sizeof(int)); //요소의 개수가 (nx+1)인 int형 배열 x생성
	for(int i=0; i<nx; i++) 
	{
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	printf("검색값:");
	scanf("%d",&ky);
	
	int idx = serach(x,nx,ky); //배열 x에서 값이 ky인 요소를 선형 검색
	if(idx ==-1) 
		printf("검색 실패");
	else
		printf("%d는 x[%d]에 있습니다.",ky,idx);
		
	free(x);
	
	return 0;
}

 

1) 검색값 key를 보초로 a[n]에 대입

a[n] = key;

2) 배열 요소를 순서대로 검사

while(1) {
    if(a[i] == key)
    	break;
    i++;
}

3) while문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단

 

 - 변수 i값이 n일때 

  -> 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환

 

 - 변수 i값이 n이 아닐때 

  -> 찾은 값이 원래 데이터이므로 i값을 반환

return i==n?-1:i;