[자료구조]이진 탐색(Binary Search)

이진 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값을 비교하는 방식입니다.

선택한 중앙값을 기준으로 찾고자 하는 값보다 크다면 기준의 왼쪽 범위에서, 찾고자 하는 값보다 작다면 기준의 오른쪽 범위에서 다시 중앙값을 선택하여 반복합니다.

 

이진 탐색 과정을 그림으로 보자면 다음과 같습니다.

위 그림에서 보면 길이가 10인 리스트에 { 0,2,4,6,8,10,12,14,16,18 } 값이 정렬되어 저장되어 있고, 여기서 12를 찾는 과정입니다.

처음에 중앙값, (length / 2)인 5를 기준으로 합니다. 리스트의 5번 index의 값을 기준으로 하는 겁니다. 리스트의 5번 index의 값은 10으로 찾고자 하는 값 보다 작습니다. 따라서 기준의 오른쪽에서 다시 시작합니다.

length가 4인 리스트에서 중앙값, (length / 2)인 2를 기준으로 합니다. 리스트의 2번 index의 값은 16으로 찾고자 하는 값 보다 큽니다. 따라서 기준의 왼쪽에서 다시 시작합니다. 

length가 2인 리스트에서 중앙값, (length / 2)인 1을 기준으로 합니다. 리스트의 1번  index의 값은 14로 찾고자 하는 값 보다 큽니다. 따라서 기준의 왼쪽에서 다시 시작합니다.

length가 1인 리스트에서 중앙값, (length / 2)인 0을 기준으로 합니다. 리스트의 0번 index의 값은 12로 찾고자 하는 값과 같습니다. 이제 탐색을 그만둡니다.

이진 탐색의 성능

이진 탐색은 특성상 정렬된 리스트에만 사용할 수 있는 단점이 있습니다. 하지만 검색이 반복될 때마다 목푯값을 찾을 확률이 2배가 되므로 속도가 빠르다는 장점이 있습니다.

 

수식으로 보자면 한 번 비교를 할 때마다 범위가 1/2로 줄어듭니다. 

위의 데이터 집합의 크기를 n이라 하고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어집니다.

k=log2(n)이 되므로 데이터 집합의 크기가 약 43억 개 라면 최대 32회의 탐색으로 데이터를 찾을 수 있습니다.

 

 

<Code1>

int main()
{
	int arData[10] = { 0,2,4,6,8,10,12,14,16,18 };
	int nSearch = 0;
	const int* pData = nullptr;

	scanf_s("%d", &nSearch);
	pData = bSearch(arData, 10, nSearch);
	if (pData != nullptr) {
		printf("%d \n", *pData);
	}
	else {
		printf("search fail \n");
	}

    return 0;
}

const int * bSearch(const int * pData, int nLength, int nSearch)
{
	const int* pTmp = nullptr;
	int nLen = 0;
	int nPivot = 0;

	nLen = nLength;
	nPivot = nLen / 2;
	pTmp = pData;
	while (nLen > 0 && pTmp[nPivot] != nSearch) {
		if (pTmp[nPivot] < nSearch) {
			pTmp = pTmp + nPivot + 1;
			nLen -= (nPivot + 1);
		}
		else if (pTmp[nPivot] > nSearch) {
			nLen = nPivot;
		}
		nPivot = nLen / 2;
	}

	if (nLen <= 0) {
		return nullptr;
	}
	return pTmp + nPivot;
}

위 코드에서 bSearch() 함수가 이진 탐색을 하는 함수입니다.

리스트의 길이가 0보다 크고, 기준 값이 찾는 값과 다를 때 반복을 진행합니다.

만약 찾는 값과 기준 값이 같다면 반복을 빠져나와 그 포인터 값을 반환합니다.

만약 찾는 값이 리스트에 없다면 길이가 0이 되어 반복을 빠져나오게 되고 이때에는 nullptr을 반환하여 리스트에 찾는 값이 없다는 것을 알려줍니다.

 

 

<Code2>

이진 탐색을 재귀적인 방식으로 구현할 수 있습니다.

const int * bSearch(const int * pData, int nLength, int nSearch)
{
	if (nLength <= 0) {
		return nullptr;
	}

	int nPivot = 0;
	nPivot = nLength / 2;
	if (pData[nPivot] < nSearch) {
		pData = pData + nPivot + 1;
		nLength -= (nPivot + 1);
		return bSearch(pData, nLength, nSearch);
	}
	else if (pData[nPivot] > nSearch) {
		nLength = nPivot;
		return bSearch(pData, nLength, nSearch);
	}

	return pData + nPivot;
}

bSearch() 함수는 리스트의 기준 값과 찾는 값이 같다면 그 값의 포인터를 반환합니다.

기준 값이 찾는 값 보다 크거나 작을 경우 다시 bSearch() 함수를 호출하도록 합니다.

만약 리스트의 길이가 0보다 같거나 작을 때까지 기준 값이 찾는 값과 같은 경우가 없다면 nullptr을 반환합니다.