알고리즘

이분 검색

이분 검색이란

• 이분 검색은 구간의 중간값과 키값의 대소를 구분하여 테이블을 절반씩 나눠가며 비교하는 방식이다.
• 한 번 비교할 때마다 테이블의 길이가 절반씩 줄어들기 때문에 검색 효율은 상당히 좋은 편이며 테이블이 커도 속도가 느려지지 않는다.
• 일반적으로 우리가 영한 사전을 검색할 때 이분 검색을 사용한다.
• 이분 검색이 가능하려면 테이블의 모든 자료가 오름차순으로 정렬되어 있어야 한다는 조건이 있다.

코드 해설

• 배열 ar이 검색 대상 테이블이며 19개의 정수들이 크기 순으로 나열되어 있다.
• BinarySearch 함수는 이 배열에서 key를 찾는데 29라는 수가 키 값으로 주어졌다.
  

int ar[19];
n = 배열의 길이;

lower = 0;
middle = 0;
upper = n-1;

변수 세 개를 설정한다.

for(;;)
{
	middle = (upper + lower) / 2;
    
    if(ar[middle] == key) printf("찾았습니다.") break;
    
    if (ar[middle] > key)
    {
    	upper = middle - 1;
    }
    else
    {
    	lower = middle + 1;
    }
    
    if (upper < lower)
    {
    	printf("불합격하셨습니다.");
        break;
    }
}

1. arr[0] ~ arr[18] 의 가운데 수인 arr[9] (middle)를 찾는다.
2. 그 수가 key값보다 큰 지, 작은 지, key 값인지를 비교한다.
3. key값을 찾을 경우 그대로 출력한다.
4. arr[middle]의 값이 값보다 arr[i]의 값이 크면 upper(최댓값)의 수를 arr[middle-1]의 값으로 설정한다. 반대의 경우 lower(최솟값)의 값을 arr[middle+1]을 한다.
5. upper보다 lower의 값이 큰 경우에는 찾을 수 없다는 의미이다.
6. middle의 값이 key값이 될 때까지 반복한다.

---

key값을 입력받고 합격자와 불합격자 출력하기

내 코드

#include<stdio.h>

int BinarySearch(int* arr, int n, int key);

void main()
{
	int arr[] = { 2,6,13,19,21,21,23,29,35,48,62,89,90,95,99,102,109,208,629 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int key = 0;

	printf("수험번호를 입력하세요 : ");
	scanf_s("%d", &key);

	int ret = BinarySearch(arr, n, key);

	if (ret == -1)
	{
		printf("불합격하셨습니다.\n");
	}
	else {
		printf("축하합니다. 합격하셨습니다.\n");
	}
}

int BinarySearch(int* arr, int n, int key)
{
	int lower = 0;
	int middle = 0;
	int upper = n - 1;

	for (int i = 0; i <= upper; i++)
	{
		middle = (upper + lower) / 2;

		if (arr[middle] == key)
		{
			return middle;
		}

		if (arr[middle] > key)
		{
			upper = middle - 1;
		}
		else
		{
			lower = middle + 1;
		}

		if (upper < lower)
		{
			return -1;
		}
	}
}

알고리즘을 작성하고 함수로 빼는 방법에 대해서는 강사님 코드가 많이 도움이 됐다.
처음 문제를 보고서는 for문 안에 for문을 반복해서 쓰는 걸까? 싶었지만 역시 그럴리가 없지...싶었다ㅠ ㅠ