[자료구조] 이원/이진 탐색(binary search)에 대하여

Data_Structure

 

 

 

 

 

 

 

 

이원/이진탐색에 대하여

About. Binary Search

 

 

---

 

 

 

---

!이론 설명!

---

 

 

 

우리가 단어가 100개 등록되어있는 사전에서 단어를 알아서 찾아주는 프로그램을 작성한다고 합시다.

 

 

그러면 우리가 생각할 수 있는 알고리즘 중 가장 쉬운 방법은 첫번째부터 100번째까지,

 

찾는 단어와 사전에 등록되어있는 단어를 같은지 비교하는 알고리즘이 있겠죠.

 

우선 이런 알고리즘을 이용을 한다면 구현하기에는 매우 쉽겠지만,

 

사전 후반에 있는 단어들을 찾는 경우나, 사전에 등재되어있지 않은 단어를 찾는 경우

 

무조건 비교과정을 100번가까이 반복해야하는 점이 효율적이지 못하다고 할 수 있겠죠.

 

 

 

 

 

그래서 이런 상황에서는 이원 탐색을 이용하면 더 효율적인 알고리즘을 구현할 수 있습니다.

 

이원 탐색에 대한 설명은 간단하게 설명하기 위해 단순 숫자배열로 설명하겠습니다.

 

 

 

 

이렇게 인덱스가 7개인, 위와같은 배열이 있다고 합시다.

 

이 상황에서 저는 숫자 8을 찾고 싶다고 가정합시다.

 

 

 

 

 

인덱스 0부터 8이 있는지 비교하는 대신, 배열의 중앙값과 내가 찾고싶은 값을 비교합니다.

 

만약에 내가 찾고자하는 값이 7보다 작으면 7을 기준으로 왼쪽 반을 찾아볼 것이고,

 

만약에 내가 찾고자하는 값이 7보다 크면 7을 기준으로 오른쪽 반을 찾아보면 되겠죠.

 

그럼 이경우에는 7 < 8 이니 오른쪽 반을 봅시다!

 

 

 

 

이제 오른쪽 반을 기준으로, 3개 중 중간값은 9이니 9와 8을 비교를 하면 8 < 9 이므로 

 

7보다는 크고, 9보다는 작은 값을 찾으면...?

 

 

 

 

 

 

자란, 우리가 찾고있었던 값 8을 찾게 되었습니다!

 

단순 비교 알고리즘을 이용했다면 5번걸렸을것을, 이원 탐색 알고리즘을 이용하니 총 3번의 비교로 찾을 수 있었네요.

 

이 예시로 보면 5번이나, 3번이나 거기서 거기 아닌가? 라고 생각할 수도 있지만

 

배열의 크기가 7개가 아닌 70개, 7000개로 늘어난다면 이 알고리즘의 효율은 더욱 극대화되겠죠:)

 

 

---

!효율성!

---

 

 

 

 

효율 얘기가 나와서 잠깐 수학시간을 가져보자면,

 

총 크기가 n인 배열에대해 이원탐색을 진행하면 매번 배열의 크기가 반으로 줄어드는 것과 같으므로, 계속 반으로 줄어들다가 값이 1이되면 우리가 원하는 값을 찾았다고 볼 수 있겠죠.

 

찾는데까지 걸리는 횟수를 k라고 두고, 그 식을 정리해주면

 

 

 

이런 로그식이 나오게됩니다. 즉 이원탐색은 값이 많아질수록 효율적인 알고리즘이라는 것도 알 수 있겠네요!

 

 

 

---

!코드!

---

 

우선 이 알고리즘을 사용하기 위해서는 기본적으로 배열이 오름차순/내림차순으로

배열이 되어 있어야 한다는 것을 알 수 있습니다.

 

그럼 그걸 이용하기 위해서는 다양한 정렬 알고리즘을 사용할 수 있겠죠.

혹시라도 궁금하시다면 아래 링크들을 참고하는것도 좋을 것 같아요:)

 

https://dokhakdubini.tistory.com/172

[자료구조] 선택정렬(Selection Sort)에 대하여

 

 

일단 의사코드를 작성해보면 다음과 같습니다.

 

 

while (there are more integers to check){
	middle = (left + right) / 2;
    if (searchnum < list[middle])
    	right = middle - 1;
    else if (searchnum == list[middle])
    	return middle;
    else
    	left = middle + 1;
}

 

 

위에 설명한 것과 같고, 이 코드에서 중요한 점은 searchnum의 범위에 따라 left/right, 즉 우리가 봐줘야할 구간을 설정해주는 것이 중요하네요.

 

 

 

#include<stdio.h>

//size 크기의 data배열안에서 searchnum을 찾기
//값이없으면 -1반환
//값이 있으면 data배열의 index 반환
int binarySearch(int data[], int size, int searchnum){
	int left = 0; //시작
	int right = size - 1; //끝
	int middle;
	while (left <= right) {
		middle = (left + right) / 2;
		if (data[middle] == searchnum) return middle;
		else if (data[middle] > searchnum) right = middle - 1;
		else left = middle + 1;
	}
	return -1;
}

int main() {
	int searchnum;
	int data[] = { 1,3,6,8,11,23,111,114,213 };
	int dataSize = sizeof(data) / sizeof(int);
	for (int i = 0; i < 9 ; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	printf("찾을 숫자: ");
	scanf("%d", &searchnum);
	int ans = binarySearch(data, dataSize, searchnum);
	printf("%d번째 인덱스, 값: %d\n", ans+1, data[ans]);
}

 

이렇게 하는 방법도 있고, 수업시간에 배운 알고리즘이 더 효율적인 것 같아 이것도 올립니다.

 

#include <stdio.h>

int binsearch(int list[], int searchnum, int left, int right);
int compare(int x, int y);

int main() {
	int searchnum;
	int arr[7] = {1, 2, 3, 4, 5, 6, 7 };
	printf("searchnum: ");
	scanf("%d ", &searchnum);

	binsearch(arr, searchnum, 0, 6);
}

int compare(int x, int y) {
	if (x < y)
		return -1;
	else if (x == y)
		return 0;
	else
		return 1;
}

int binsearch(int list[], int searchnum, int left, int right) {
	int middle;
	while (left <= right) {
		middle = (left + right) / 2;
		switch (compare(list[middle], searchnum)) {
		case -1:
			left = middle + 1;
			break;
		case 0:
			return middle;
		case 1: 
			right = middle - 1;
		}
	}
	return -1;
}

 

참고하시길!

 

 

 

 

참고: https://blog.hexabrain.net/246

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98