(C/C++) 검색 - 이분 탐색, 이진 탐색 (Binary Search), 보간탐색(Interpolation Search)

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다.

1. 이분 탐색, 이진 탐색 (Binary Search)

평균적으로 log²N 의 검색길이를 갖는 빠른 검색방법입니다.

다만 이분검색은 데이터들이 정렬되어 있어야 합니다.

또한 검색은 쉬운데 삽입 삭제가 조금 까다롭다고 생각하시면 됩니다.

즉 삽입 삭제가 빈번이 일어나는 데이터보다 검색만을 위한 데이터를 위해 사용하는게 좋습니다.

 

2. 구현 방법

이미 정렬된 데이터 집합에 중간값과 내 키의 값을 비교하여 왼쪽 혹은 오른쪽 구간을 선택,

그 구간의 중간값과 키값을 비교 하는 재귀적인 과정을 통해 검색이 완료됩니다.

검색은 중간값과 키값이 일치할떄까지 구간을 반으로 나누는 작업을 진행하며 키값을 찾습니다.

삽입은 어느위치에 넣어야 정렬이 유지되는지 위치를 찾고 그 위치로부터 한칸씩 뒤로 밀고 삽입합니다.

삭제는 삭제할 키의 위치를 찾고 한칸씩 앞으로 당깁니다.

 

3. 배열을 이용한 이진 탐색 구현

struct Data
{
	int key;
	int phone;
};

class BinaryArray
{
private:
	Data* arrays;
	int maxCnt;
	int currentCnt;

	bool FineIndex(int key, int& index);
public:
	BinaryArray(int max = 100);
	~BinaryArray();
	bool Search(int key, Data& data);
	bool Insert(Data data);
	bool Delete(int key);
	void PrintAll();
};

이진 탐색의 헤더 입니다.

Data 구조체를 선언했고 내부 연산에 필요한 FindIndex 함수를 Private 로 선언했습니다.

 

#include "BinaryArray.h"
#include <stdio.h>

bool BinaryArray::FineIndex(int key, int& index)
{
	int mid;
	int left = 0;
	int right = currentCnt;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arrays[mid].key == key)
		{
			index = mid;
			return true;
		}
		else if (arrays[mid].key < key)	//mid index에 있는 값이 찾는값보다 작으면 오른쪽에서 찾는다.
			left = mid + 1;
		else if (arrays[mid].key > key)	//mid index에 있는 값이 찾는값보다 크면 왼쪽에서 찾는다.
			right = mid - 1;
	}
	return false;
}

BinaryArray::BinaryArray(int max)
{
	maxCnt = max;
	currentCnt = 0;
	arrays = new Data[maxCnt];
}

BinaryArray::~BinaryArray()
{
	delete[] arrays;
}

bool BinaryArray::Search(int key, Data& data)
{
	int index;
	if (FineIndex(key, index))
	{
		data = arrays[index];
		return true;
	}

	return false;
}

bool BinaryArray::Insert(Data data)
{
	if (currentCnt >= maxCnt)
		return false;

	int index = 0;
	while (data.key > arrays[index].key && index < currentCnt)	//오름차순으로 넣는다.
		index++;

	for (int i = currentCnt; i > index; i--)
	{
		arrays[i] = arrays[i - 1];
	}
	arrays[index] = data;
	currentCnt++;
	return true;
}

bool BinaryArray::Delete(int key)
{
	int index;
	if (FineIndex(key, index))
	{
		for (int i = index + 1; i < currentCnt; i++)
		{
			arrays[i - 1] = arrays[i];
		}
		currentCnt--;
		return true;
	}
	return false;
}

void BinaryArray::PrintAll()
{
	for (int i = 0; i < currentCnt; i++)
	{
		printf("key : %d\tPhone : %d\n", arrays[i].key, arrays[i].phone);
	}
}

이진 탐색의 CPP 입니다.

오름차순으로 정렬을 했고(작은 값이 앞으로) 그에 맞춰 검색을 하고 있습니다.

삽입시 뒤로, 삭제시 앞으로 배열을 이동해 주었습니다.

 

4. 이진 탐색의 개선 보간 탐색 (Interpolation Search)

이진 탐색을 할 데이터들이 고르게 분포되어 있다면 보간탐색을 사용하는 것이 더 짧은 평균 탐색 시간을 가집니다.

반대로 고르지 못한 데이터들을 검색한다면 시간이 좀 더 걸릴 수 있습니다.

위 이진 탐색에서 실질적으로 탐색하는 부분인 FineIndex 함수를 수정만 하면 됩니다.

이진 탐색이랑 가장 큰 차이점은 이진 탐색은 데이터들의 중간 값 mid 를 찾아 줄여 나가는 것이고

보간 탐색은 mid 가 아니고 찾는 값이 상대적으로 작다면 앞쪽에서, 크다면 뒤쪽에서 찾아 줄여나가는 방식입니다. 

bool BinaryArray::FineIndex(int key, int& index)
{
	int findIndex;
	int left = 0;
	int right = currentCnt;
	while (left <= right)
	{
		if (arrays[left].key > key || arrays[right -1].key < key)	//보간탐색 예외처리
			return false;
		
       	 	//보간 탐색은 mid 를 구하지 않는다.
		findIndex = left + (right - left) * (double)(key - arrays[left].key) / (arrays[right - 1].key - arrays[left].key);
		if (arrays[findIndex].key == key)
		{
			index = findIndex;
			return true;
		}
		else if (arrays[findIndex].key < key)	//findIndex에 있는 값이 찾는값보다 작으면 오른쪽에서 찾는다.
			left = findIndex + 1;
		else if (arrays[findIndex].key > key)	//findIndex에 있는 값이 찾는값보다 크면 왼쪽에서 찾는다.
			right = findIndex - 1;
	}
	return false;
}

if (arrays[left].key > key || arrays[right -1].key < key) return false;

findIndex = left + (right - left) * (double)(key - arrays[left].key) / (arrays[right - 1].key - arrays[left].key);

이진 탐색에서 이 두 구간이 변경되었습니다.

감사합니다.