Binary Search 응용 문제

/*
Q2. **이진 검색 프로그램**을 작성하라.
	p.122 연습 문제 4처럼 이진 검색 과정을 자세히 출력하라. 
	순서도 포함.
	선형검색과 이진검색의 속도를 비교하라.
*/

 

문제 요구 사항

* Binary Search 를 이용해서 값을 탐색하고, Linear Search와 시간복잡도를 비교해 볼 것

 

 

---

 

이진 탐색(Binary Search)

1. 전제조건 : 데이터가 키 값으로 이미 정렬되어 있어야 한다.
2. 중앙 값을 찾는 값과 비교하여 찾는 값이 더 크다면 중앙값의 오른쪽을 탐색하고, 찾는 값이 더 작다면 중앙값의 왼쪽을 탐색한다.
3. 시간 복잡도: O(logN)
4. 장점: 대용량 데이터에서 특정 값의 위치를 찾는 것에 용이하다.
5. 단점: 검색 대상의 생성, 수정에 취약하다.

 

---

 

이진 탐색(Binary Search) 코드

void BinarySearch(int nums[], long long find_num)
{
	int start = 0, end = MAX-1;

	while (start <= end)
	{
		int middle = (start + end) / 2;
		if (nums[middle] == find_num)
		{
			//cout << find_num << "은 nums[" << middle << "]에 존재합니다.\\n";
			break;
		}
		else if (start == end)
		{
			//cout << find_num << "은 nums에 존재하지 않습니다.\\n";
			break;
		}
		else if (find_num > nums[middle])
		{
			start = middle+1;
		}
		else if (find_num < nums[middle])
		{
			end = middle-1;
		}
	}
}

 

 

선형 탐색(Linear Search) 코드

void LinearSearch(int nums[], long long find_num)
{
	for (int i = 0; i < MAX; i++)
	{
		if (nums[i] == find_num)
		{
			//cout << find_num << "은 nums[" << i << "]에 존재합니다.\\n";
			return;
		}
	}
	//cout << find_num << "은 nums에 존재하지 않습니다.\\n";
}

 

 

전체 코드

밑의 전체 코드는 동일한 탐색 조건에서 위의 두 코드의 수행 시간을 비교해 본 것이다. Show____Search() 함수는 ‘Do it! 알고리즘’ 책에서 요구하는 출력 형식에 맞추어서 출력하는 함수다. 출력 부분을 제외하고는 위의 Binary Search, Linear Search 와 방식이 똑같다.

#define MAX 100'000

void LinearSearch(int nums[], long long find_num);
void BinarySearch(int nums[], long long find_num);

void ShowLinearSearch(int nums[], long long find_num);
void ShowBinarySearch(int nums[], long long find_num);

int nums[MAX];

int main()
{
	clock_t start, end;
	long long find_num;

	// 0~MAX-1 인덱스까지 1~MAX의 값을 넣는다 
	for (int i = 0; i < MAX; i++)
	{
		nums[i] = i + 1;
	}

	/*========================Binary Search========================*/
	start = clock();
	for (int i = 0; i < MAX; i++)
	{
		find_num = i + 1;
		BinarySearch(nums, find_num);
	}
	end = clock();
	cout << "Binary Search 시간: " << (double)(end - start)/CLOCKS_PER_SEC << " ms" << endl;

	clock_t start1, end1;
	/*========================Linear Search========================*/
	start1 = clock();
	for (int i = 0; i < MAX; i++)
	{
		find_num = i + 1;
		LinearSearch(nums, find_num);
	}
	end1 = clock();
	cout << "Linear Search 시간: " << (double)(end1 - start1) / CLOCKS_PER_SEC << " ms" << endl << endl;

}

void LinearSearch(int nums[], long long find_num)
{
	for (int i = 0; i < MAX; i++)
	{
		if (nums[i] == find_num)
		{
			//cout << find_num << "은 nums[" << i << "]에 존재합니다.\\n";
			return;
		}
	}
	//cout << find_num << "은 nums에 존재하지 않습니다.\\n";
}

void BinarySearch(int nums[], long long find_num)
{
	int start = 0, end = MAX-1;

	while (start <= end)
	{
		int middle = (start + end) / 2;
		if (nums[middle] == find_num)
		{
			//cout << find_num << "은 nums[" << middle << "]에 존재합니다.\\n";
			break;
		}
		else if (start == end)
		{
			//cout << find_num << "은 nums에 존재하지 않습니다.\\n";
			break;
		}
		else if (find_num > nums[middle])
		{
			start = middle+1;
		}
		else if (find_num < nums[middle])
		{
			end = middle-1;
		}
	}
}

void ShowLinearSearch(int nums[], long long find_num)
{
	cout << "# LinearSearch #\\n";
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < i; j++)
		{
			cout << "  ";
		}
		cout << "*\\n";
		for (int j = 0; j < MAX; j++)
			cout << nums[j] << " ";
		cout << endl;
		if (nums[i] == find_num)
		{
			cout << find_num << "은 nums[" << i << "]에 존재합니다.\\n";
			return;
		}
	}
	cout << find_num << "은 nums에 존재하지 않습니다.\\n";
}

void ShowBinarySearch(int nums[], long long find_num)
{
	cout << "# BinarySearch #\\n";
	int start = 0, middle = (MAX) / 2, end = MAX - 1;
	

	while (start <= end)
	{
		
		middle = (start + end) / 2;
		for (int i = 0; i < middle; i++)
		{
			cout << "   ";
		}
		cout << "*\\n";
		for (int i = 0; i < MAX; i++)
		{
			printf("%2d ", nums[i]);
			//cout << nums[i] << " ";
		}
		cout << endl;
		if (nums[middle] == find_num)
		{
			cout << find_num << "은 nums[" << middle << "]에 존재합니다.\\n";
			break;
		}
		else if (start == end)
		{
			cout << find_num << "은 nums에 존재하지 않습니다.\\n";
			break;
		}
		else if (find_num > nums[middle])
		{
			start = middle + 1;
		}
		else if (find_num < nums[middle])
		{
			end = middle - 1;
		}
	}
}

 

 

실행 결과

시간 측정 결과 ( 데이터 100,000개 기준)

 

Show___Search( ) 함수 결과