[알고리즘] 이진 탐색(이분 탐색)

📌이진 탐색(Binary Search)

주어진 배열의 중간값과 찾고자하는 키값의 대소를 비교하여, 배열을 절반으로 나누어가며 값의 유무를 탐색하는 검색 알고리즘. 중간값이 키값보다 크면 반으로 나눈 배열의 오른쪽 부분에서 다시 탐색하고, 중간값이 키값보다 작다면 왼쪽 배열에서 재탐색한다. 한 번 비교할 때마다 배열이 절반으로 줄어들게 되므로 배열의 크기가 커지더라도 검색 효율이 좋다. 시간 복잡도는 `O(logN)`.  단, 키값과 중간값의 대소를 비교하기 때문에 배열이 반드시 오름차순으로 정렬되어 있어야 한다. 

 

 

 

📌구현

언어: C

 

#include <stdio.h>

int BinarySearch(int* arrPtr, int lower, int upper, int middle, int key) {

	// 인덱스 반환
	if (arrPtr[middle] == key) {
		return middle;
	}

	// 값을 찾을 수 없음
	if (middle <= lower || middle >= upper) {
		return -1;
	}

	// key가 arrPtr[middle]보다 작으면 왼쪽, 크면 오른쪽
	if (key < arrPtr[middle]) {
		upper = middle;
	}else {
		lower = middle;
	}


	return BinarySearch(arrPtr, lower, upper, (lower + upper) / 2, key);
}


int main() {

	int arr[] = { 2,6,13,19,21,21,23,29,35,48,62,89,90,95,99,102,109,208,629 };

	int input;
	printf("값을 입력하세요:");
	scanf_s("%d", &input);

	int lower = 0;
	int upper = sizeof(arr) / sizeof(arr[0]);
	int middle = upper / 2;

	int result = BinarySearch(arr, lower, upper, middle, input);
	if(result != -1){
        printf("찾는 값은 %d번째에 있습니다.\n", result + 1);
    }else{
		printf("찾는 값이 없습니다.\n");
    }

	return 0;
}