기초컴퓨터프로그래밍 C언어(10)-탐색

1. 순차탐색
2. 이진탐색

 

탐색은 컴퓨터가 가장 많이 하는 작업 중의 하나입니다. 단순하게 여러분이 하루에 인터넷에서 필요한 자료들을 얼마나 많이 탐색하는지를 생각해보면 되죠. 탐색은 많은 시간이 요규되는 작업이므로 효율적으로 수행하는 것은 매우 중요합니다.

오늘 포스팅에서는 순차 탐색과 이진탐색을 살펴보겠습니다.

 

순차탐색

순차탐색은 탐색 방법중에서 가장 간단하고 직접적인 탐색방법입니다. 순차 탐색은 배열의 원소를 순서대로 하나씩 꺼내서 탐색키와 비요해 원하는값을 찾아가는 방법입니다. 순차 탐색은 일치하는 항복을 찾을때까지 비교를 계속합니다. 순차 탐색은 첫번째 원소에서 성공할 수도있고 마지막 원소까지 가야하는 경우도 있습니다. 평균적으로는 절반 정도의 배열 원소와 비교해야 합니다.

#include<stdio.h>
#define SIZE 16

int main() {
	int key;
	int list[SIZE] = { 2,6,11,13,18,20,22,27,29,30,34,38,41,42,45,47 };

	printf("탐색할 값을 입력하시오");
	scanf("%d", &key);

	for (int i = 0; i < SIZE; i++) {
		if (list[i] == key)
			printf("탐색 성공 인덱스 =%d\n", i+1);
	
	}

	printf("탐색 종료\n");
}

출력화면

 

• 메인 함수와 배열 초기화
  • int main(): 프로그램의 진입점입니다.
  • int key: 사용자가 입력할 값을 저장할 변수입니다.
  • int list[SIZE]: 탐색할 배열로, 16개의 정수로 초기화됩니다.

    int main() {
        int key;
        int list[SIZE] = { 2, 6, 11, 13, 18, 20, 22, 27, 29, 30, 34, 38, 41, 42, 45, 47 };
    

• 사용자 입력 받기
  • printf("탐색할 값을 입력하시오: ");: 사용자에게 값을 입력하라는 메시지를 출력합니다.
  • scanf("%d", &key);: 사용자가 입력한 값을 key 변수에 저장합니다.

    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key);
    

• 순차탐색 루프
  • for (int i = 0; i < SIZE; i++): 배열의 처음부터 끝까지 반복합니다.
  • if (list[i] == key): 배열의 현재 요소가 사용자가 입력한 값과 일치하는지 검사합니다.
  • printf("탐색 성공 인덱스 = %d\n", i + 1);: 탐색에 성공했을 경우 해당 요소의 인덱스를 출력합니다.

    for (int i = 0; i < SIZE; i++) {
        if (list[i] == key)
            printf("탐색 성공 인덱스 = %d\n", i + 1);
    }
    

 

 

이진탐색

1024개의 원소를 가지는 배열을 탐색하는데 얼마만큼의 비교가 필요할까요? 한번 비교할때마다 탐색범위가 절반씩 줄어듭니다. 첫 번째 비교를 하면 범위가 512로 줄어들고 이후로 비교할때마다 범위가 256,128,64,32,16,8,4,2,1이 됩니다. 범위가 1이되면 이미 탐색이 성공하던지 실패하던지 하겠죠. 이건 최악의 경우를 가정한것이고 중간에 만약 일치하는 원소가 있으면 탐색이 종료됩니다. 따라서 2^10=1024이므로 최대 10번의 비교만 있으면 됩니다.

이진 탐색에서는 비교가 이루어질때마다 탐색 범위가 급격히 줄어듭니다. 즉 찾고자 하는 항복이 속해져있지 않은 부분은 전혀 고려할 필요가 없기 때문입니다. 이러한 방법을 반복적으로 사용하는것을 이진탐색이라 합니다.

#include<stdio.h>
#define SIZE 16
int binary_search(int list[], int n, int key);

int main() {
	int key;
	int grade[SIZE] = { 2,6,11,13,18,20,22,27,29,30,34,38,41,42,45,47 };

	printf("탐색할 값을 입력하시오: ");
	scanf("%d", &key);
	printf("탐색 결과=%d\n", binary_search(grade, SIZE, key));
	return 0;
	}
int binary_search(int list[], int n, int key) {
	int low, high, middle;
	low = 0;
	high = n - 1;

	while (low <= high) {
		printf("[% d % d]\n",low,high);
		middle =(low+high)/2;
		if (key == list[middle])
			return middle;
		else if (key > list[middle])
			low = middle + 1;
		else
			high = middle - 1;

	}
	return -1;
}

출력화면

 

 

• int binary_search(int list[], int n, int key);: 이진 탐색 함수를 선언합니다.
• int main() {...}: 프로그램의 진입점인 main 함수를 정의합니다.
  • int key;: 탐색할 값을 저장할 변수를 선언합니다.
  • int grade[SIZE] = { ... };: 정렬된 정수 배열을 초기화합니다.
  • printf("탐색할 값을 입력하시오: ");: 사용자에게 탐색할 값을 입력하라는 메시지를 출력합니다.
  • scanf("%d", &key);: 사용자가 입력한 값을 key 변수에 저장합니다.
  • printf("탐색 결과=%d\n", binary_search(grade, SIZE, key));: 이진 탐색 함수를 호출하여 탐색 결과를 출력합니다.
• int binary_search(int list[], int n, int key) {...}: 이진 탐색 함수를 정의합니다.
  • int low, high, middle;: 이진 탐색에 필요한 변수를 선언합니다.
  • low = 0; high = n - 1;: 배열의 처음과 끝 인덱스를 초기화합니다.
  • while (low <= high) {...}: low가 high보다 작거나 같을 때까지 반복합니다.
    • printf("[%d %d]\n", low, high);: 현재 low와 high 값을 출력합니다.
    • middle = (low + high) / 2;: 중간 인덱스를 계산합니다.
    • if (key == list[middle]) return middle;: key가 중간 값과 같으면 해당 인덱스를 반환합니다.
    • else if (key > list[middle]) low = middle + 1;: key가 중간 값보다 크면 low를 중간 인덱스 + 1로 설정합니다.
    • else high = middle - 1;: key가 중간 값보다 작으면 high를 중간 인덱스 - 1로 설정합니다.
  • return -1;: key를 찾지 못한 경우 -1을 반환합니다.

 

 

이코드는 위에서 middle에있는 +1과 -1을 지웠을때입니다. 결과는 1감소했지만 돌아가기는 하죠? 배열의 인덱스가 0일때부터 카운팅이됐네요. 이코드는 효율적이지 못한 코드긴합니다.

이진 탐색 알고리즘은 일반적으로 효율적이지만, 특정 상황에서 최적화되지 않을 수 있습니다. 예를 들어, middle + 1과 middle - 1을 사용하지 않는 경우, 반복문 내부에서 불필요한 계산이 발생할 수 있습니다. 이러한 부분을 개선하면 더 효율적인 코드가 될 수 있습니다.

middle + 1과 middle - 1을 사용하여 탐색 범위를 좁히는 것을 최적화하지 않는 경우, 반복문의 횟수가 늘어나고, CPU의 계산 비용이 증가할 수 있습니다. 이진 탐색은 배열이 정렬된 상태에서 빠르게 찾는 알고리즘이므로, 탐색 범위를 정확히 조절하는 것이 중요합니다.

 

여기서 잠간 만약 int grade [size]의 배열이 난수로 생성되면? 이진탐색을 사용할 수없습니다. 이진탐색은 기본적으로 정렬이 되었을때만 사용가능한점 꼭 기억해주세요.