이진 탐색 (feat. 백준14425번)

1. 이진탐색이란?

이진탐색(Binary Search)은 처음부터 끝까지 모든 케이스를 탐색하는 일반적인 선형탐색(Linear Search)와 달리 데이터의 배열의 중간값을 확인해보고 해당값보다 크거나 작은 경우를 체크해가며 탐색해야하는 데이터를 반씩 줄여나가는 탐색방법이다.

 

만약 n개의 데이터가 들어있는 배열 arr[n] 이 있다고 가정하면, 일반적인 선형탐색의 경우 처음부터 모든 데이터를 확인해봐야하기 떄문에 데이터를 탐색하는데 O(n)이 걸리게된다. 만약 탐색해야하는 데이터가 n개이고 찾아야 하는 데이터 또한 n개라고 가정해보면 O(n) 탐색을 총 n번 해야하므로 O(n^2)의 시간이 걸리게된다.

 

2. 설명

데이터를 탐색해야하는 다음과 같은 배열이 있다고 가정하자.

arr = [1, 2, 3, 4, 5, 6, 7] 

 

여기서 찾아야 하는 값(target) = 2 라고 설정한다.

 

start = 1 (배열의 첫번째 위치)

end = 7 (배열의 마지막 위치)

mid = 4 ( start + end ) / 2 (소수점 이하는 버림)

 

위와같이 초기 세팅이 이루어진다.

 

그런다음 배열의 가운데 값(arr[mid]) 를 찾고자하는 값(target)과 비교한다. 

arr[mid] = arr[4] = 4 > 2(target) : target 보다 mid에 위치한 값이 더 작다. 즉, target은 현재 mid의 위치보다 왼쪽에 존재하는것이므로 mid를 포함한 mid 오른쪽의 값은 체크할 필요가 없다(무조건 target보다 큰값일것이므로)

 

start = 1

end = 3 (mid - 1)

mid = 2

 

따라서 체크해야하는 범위를 1 ~ mid - 1까지로 정정한뒤 다시 동일한 탐색을 진행한다

 

arr[mid]의 값은 2 이고 찾고자 하는 값 또한 2이므로 찾고자 하는 값의 인덱스를 찾음 -> 해당 인덱스 리턴

 

위와같은 과정을 수행하면 성공적으로 이진탐색을 수행 할 수 있다.

 

만약 target이 mid값보다 큰경우에는 target은 무조건 mid의 오른쪽에 존재하고 mid를 포함한 왼쪽값은 target보다 작다는게 확정이므로 start = mid + 1로 수정하여 mid + 1 ~ end 까지 탐색을 진행하면된다.

 

int binary_search(string target, int start, int end) {
	int mid = (start + end) / 2; 

	if (start > end)
		return 0;

	if (vec[mid] == target)
		return mid;

	else if (vec[mid] > target) 
		binary_search(target, start, mid - 1);
	else 
		binary_search(target, mid + 1, end);
}

3. 예제

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

위 문제의 경우 총 n개의 단어가 있는 데이터 집합 S가 있고 총 m개의 단어가 있는 다른 집합(R이라고 가정) 이 있을 때 집합 S의 단어들 중 집합 R에 속한 단어가 몇개인지 찾는 문제이다.

 

처음에는 단순히 집합 R의 모든 단어들을 순차 탐색을 통해 현재 검사하고자하는 단어(집합 S에 속한) 와 동일한 단어가 있는지 체크하는 방식으로 문제를 풀었다. 답은 성공적으로 도출했지만 시간초과가 발생했다. 한개의 단어를 탐색하는데 모든 R의 단어를 탐색하므로 10000이 걸리고 이러한 연산을 모든단어에 대해 수행하므로 다시 10000번 그런데 여기서 단어가 최대 500이므로 최악의 경우 10000 * 10000 * 500 의 연산을 수행해야하고, 1억이 보통 1초로 잡으니까 총 500초나 걸리게된다.

 

따라서 순차 탐색이아닌 이진탐색을 수행하여 탐색 시간을 줄였고 탐색시간이 O(logn)이 걸리므로 10000 * 14 * 500 으로 시간제한인 2초내에 충분히 연산이 가능하여 통과하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;
vector<string> vec;

int cnt = 0;

void binary_search(string target, int start, int end) {
	int mid = (start + end) / 2; 

	if (start > end)
		return ;

	if (vec[mid] == target) {
		cnt++;
		for (int i = mid -1; i > 0; i--) {
			if (vec[i] == target)
				cnt++;
			else
				break;
		}

		for (int i = mid +1; i < vec.size(); i++) {
			if (vec[i] == target)
				cnt++;
			else
				break;
		}

		return;

	}

	else if (vec[mid] > target) {
		 binary_search(target, start, mid - 1);
	}
	else {
		 binary_search(target, mid + 1, end);
	}

}

int main() {

	int n, m;
	string input;

	cin >> n >> m;


	for (int i = 0; i < n; i++) {
		cin >> input;
		answer.push_back(input);
	}

	for (int i = 0; i < m; i++) {
		cin >> input;
		vec.push_back(input);
	}

	sort(vec.begin(), vec.end());

	for (string str : answer) {
		binary_search(str, 0, m - 1);
	}
	
	cout << cnt;

	return 0;
}

단 위의 문제의경우 특정 단어를 찾았다고 리턴하는것이 아닌 모든 단어를 찾아야 했기떄문에 이진탐색을 통해 찾으려는 단어를 찾으면 cnt 값을 증가시켜주고 다른 단어가 나올떄 까지 해당 인덱스의 왼쪽과 오른쪽을 확인하여 동일한 단어가 있는지 체크하는 로직을 추가하여야 통과 할 수 있었다.