8.2 선형 탐색(linear search)
(0) 문제 정의
버블 정렬 프로그램으로 파일에 저장한 데이터를 읽어 배열에 저장하고, 사용자로 부터 정수를 입 력받아 그 수가 배열에 존재하는지 탐색하는 프로그램을 작성하라.
(1) 요구사항 분석
l 프로그램을 시작하면서 데이터 파일을 읽고, 파일 읽기가 올바로 실행되었는지 확인하기 위하여 파일에서 읽은 데이터를 한 줄에 10 개씩 출력한다.
l 사용자가 0보다 큰 수를 입력하면, 데이터 검색을 반복한다.
n 데이터가 존재하면, 몇 번째 존재하는지 출력한다.
n 데이터가 존재하지 않으면, 데이터가 없다고 출력한다.
n 사용자가 0 이하의 수를 입력하면, 프로그램을 종료한다.
파일 읽기 파일 저장
원본: 12
57 588 161 586 375 178 943 482 54 910 696 236
화면 입력 화면 출력
원본: 12
57 588 161 586 375 178 943 482 54 910 696 236
검색할 수를 입력하세요: 499 검색할 수를 입력하세요: 482 검색할 수를 입력하세요: -1
데이터가 파일에 없습니다.
데이터가 8번째에 있습니다.
탐색을 종료합니다.
(2) 자료구조 설계
int size; // 배열의 크기. 파일에서 배열의 크기를 읽는다.
int *data; // 배열을 동적으로 할당하여 연결하기 위한 포인터 FILE *fp; // 파일의 접근 정보를 가진 객체의 포인터
int key; // 사용자가 입력한 데이터 int index; // 배열에서 key를 탐색한 결과
(3) 알고리즘 설계
- 프로그램의 흐름
1. 파일에서 데이터를 읽어 배열에 저장한다.
2. 읽은 데이터를 화면으로 출력한다.
3. 다음을 반복한다.
4. 사용자의 입력을 받는다. // 루프 탈출 조건 : 0이하의 수를 입력 (교재에서 누락됨) 5. 배열에 사용자가 입력한 수가 존재하는지 검사한다.
6. 탐색 결과를 출력한다.
- 텍스트 파일을 읽는 프로그램 예시
myfile.txt 파일의 내용 1.234
예제 파일입니다.
프로그램의 화면 출력
I have read: 1.234 예제 파일입니다.
- 파일 읽기 함수 알고리즘 – 1 /* fileread.c by J-H Ahn 2019 */
#include <stdio.h>
#include <stdlib.h>
void main() {
char str[80];
float f;
FILE *fp;
errno_t err = fopen_s(&fp, "myfile.txt", "rt");
if (err != 0) {
fprintf(stderr, “error (%d) : can’t read file myfile.txt\n”, err);
exit(1);
}
fscanf_s(fp, "%f", &f);
fscanf_s(fp, "%s", str, _countof(str));
fclose(fp);
printf("I have read: %f %s\n", f, str);
}
int *read_data1(int *arrsize);
main() {
int *data=NULL, size=0;
data = read_data1(&size);
}
int *read_data1(int *arrsize) {
int *array=NULL, size=0;
size = 배열의 수; // 배열의 크기를 결정 array = malloc(size); // 배열을 할당
; // 배열에 데이터 저장
- 파일 읽기 함수 알고리즘 – 2 int read_data2(int **parray);
main() {
int *data=NULL, size=0;
size = read_data2(&data);
}
int read_data2(int **parray) {
int *array=NULL, size=0;
size = 배열의 수; // 배열의 크기를 결정 array = malloc(size); // 배열을 할당
; // 배열에 데이터 저장 *parray = array; // 간접적으로 포인터 전달 return size; // 크기 리턴
}
- 선형 탐색 : 처음부터 하나씩 순차적으로 탐색한다.
문제 : 17이 들어있는 변수의 위치를 탐색하라.
- 선형 탐색 함수 알고리즘 : int linear_search(int array[], int size, int key);
1. n=0부터 n<SIZE까지 2. 만일 key = data[n]이면
3. 배열 인덱스 n을 리턴한다.
4. 만일 key < data[n] 이면
5. 더 이상 탐색할 필요가 없으므로 반복문을 벗어난다.
6. 찾지 못했다는 의미로 -1을 리턴한다.
*arrsize = size; // 간접적으로 크기 전달 return array; // 포인터 리턴
}
8.3 이진 탐색(binary search)
(0) 문제 정의
버블 정렬 프로그램으로 파일에 저장한 데이터를 읽어 배열에 저장하고, 사용자로 부터 정수를 입 력받아 그 수가 배열에 존재하는지 탐색하는 프로그램을 작성하라.
(1) 요구사항 분석
선형 탐색 프로그램에서 탐색 방법만 다르므로 화면 입출력은 동일하다. 다만 파일에 있는 데이터 가 오름차순으로 정렬되어 있어야 한다.
파일 읽기 파일 저장
원본: 12
54 57 161 178 236 375 482 586 588 696 910 943
화면 입력 화면 출력
원본: 12
54 57 161 178 236 375 482 586 588 696 910 943
검색할 수를 입력하세요: 499 검색할 수를 입력하세요: 482 검색할 수를 입력하세요: -1
데이터가 파일에 없습니다.
데이터가 8번째에 있습니다.
탐색을 종료합니다.
(2) 자료구조 설계
int size; // 배열의 크기. 파일에서 배열의 크기를 읽는다.
int *data; // 배열을 동적으로 할당하여 연결하기 위한 포인터 FILE *fp; // 파일의 접근 정보를 가진 객체의 포인터
int key; // 사용자가 입력한 데이터 int index; // 배열에서 key를 탐색한 결과
(3) 알고리즘 설계
- 프로그램의 흐름
1. 파일에서 데이터를 읽어 배열에 저장한다.
2. 읽은 데이터를 화면으로 출력한다.
3. 다음을 반복한다.
4. 사용자의 입력을 받는다.
5. 0이하의 수를 입력하면 루프를 탈출하고 프로그램을 종료한다.
6. 배열에 사용자가 입력한 수가 존재하는지 검사한다.
7. 탐색 결과를 출력한다.
- 이진 탐색 : 탐색 구간을 1/2씩 줄이는 과정을 반복한다.
- 이진 탐색 함수 알고리즘 : int binary_search(int array[], int size, int key);
문제 : 25가 들어있는 변수의 위치를 탐색하라.
이 알고리즘은 탐색 범위를 나타내는 low, high 변수와 탐색 위치를 나타내는 center 변수를 사용한다.
l 초기화 과정으로 low=0(배열의 첫 번째 인덱스), high=SIZE-1=9(배열의 마지막 인덱스)로 설 정한다.
l 탐색 위치는 배열 탐색 구간의 중간이다. center = (low+high)/2 = 4이다.
l 키와 data[4]를 비교한다.
l 키가 더 크므로, 찾고자 하는 데이터는 data[4] 이후 에 존재한다는 것을 알 수 있다.
l low=center+1=5로 갱신하여, 탐색 구간을 data[5]
부터 data[9]로 좁힌다.
l 다시 탐색 위치를 center=(low+high)/2=7로 설정한 다.
l 키와 data[7]을 비교한다.
l 키가 더 작으므로, 찾고자 하는 데이터는 data[7] 이 전에 존재한다는 것을 알 수 있다.
l 이번에는 high=center-1=6으로 갱신하여, 탐색 구간을 data[5]부터 data[6]으로 좁혀서 다시 탐색한다.
l 탐색 과정에서 키와 같은 배열 원소를 발견하면 그 인덱스를 리턴하고, 만일 low>high로 될 때까지 키를 찾지 못한다면 탐색에 실패한 것이다.
1. low=0(배열의 첫 번째 인덱스), high=SIZE-1(배열의 마지막 인덱스)로 설정한다.
2. low<=high이면 아직 탐색할 영역이 남아 있으므로 다음을 반복한다.
3. center = (low+high)/2로 설정한다.
4. 만일 key = data[center]이면, center를 리턴한다.
5. 만일 key > data[center]이면, low=center+1로 갱신한다.
6. 만일 key < data[center]이면, high=center-1로 갱신한다.
7. 반복문을 벗어났다면, key를 찾지 못한 것이므로 -1을 리턴한다.
