[알고리즘] 이진 탐색 (Binary Search)

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

 

---

 

목차

0. Intro 

1. 이진탐색의 아이디어와 기본 구현

2. 이진탐색 응용

3. 매개변수 탐색

 

 

 

---

 

0. Intro

https://namu.wiki/w/%EC%97%85%20%EC%95%A4%20%EB%8B%A4%EC%9A%B4#toc

업 앤 다운 - 나무위키

 

위 링크를 읽어보면 이진 탐색의 수학적 핵심을 알 수 있다.

 

요약하자면 중간값만을 부르는 최적의 전략을 선택한다면 logN번으로 답을 찾을 수 있다는 것.

 

검색 범위를 절반씩 줄여 나가며 원하는 데이터를 찾는 알고리즘이 이진 탐색(이분 탐색)이다.

 

 

---

 

 

1.  이진탐색의 아이디어와 기본 구현

앞서 공부한 투포인터에서는 s++, e--를 이용하여 정답후보를 하나씩 제외해가는 방식이었다면,

 

이진 탐색은 하나씩이 아닌 두 수 값의 중앙값을 선택해 정답이 될 수 없는 값을 절반씩 제외해 가는 방식이라 할 수 있다.

(최대한 많이 정답이 될 수 없는 값을 제외하자.)

 

예를들어 [1 ~ 50]에서 특정 수를 찾는다고 할 때 다음과 같이 정답을 효율적으로 찾을 수 있다.

(이진 탐색은 중앙 값 (mid)을 볼 때, 정답 후보 절반을 없앨 수 있을 경우에 가능하다.)

정답 후보 
50개 => 25개 => 12개  => 6개 => 3개 => 1개
(log N번이면 정답을 찾을 수 있다.)

 

이를 코드로 표현해본다면 다음과 같다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> vec{ 1, 2, 5, 6, 7, 8, 10, 15, 20, 23 };
	int n = vec.size();

	// 만약 15의 인덱스를 구하고 싶다.


	// 처음 정답 후보는 0 ~ (n - 1) 인덱스 전부가
	// 정답 후보이다.
	int s = 0;
	int e = n - 1;

	// 원하는 값.
	int v = 15;

	// 답을 담을 변수

	int ans_idx = 0;
	while (1)
	{
		int mid = (s + e) / 2;

		if (vec[mid] == v)
		{
			ans_idx = mid;
			break;
		}
		// s ~ mid는 모두 정답 후보에서 제외된다.
		else if (vec[mid] < v)
		{
			s = mid + 1;
		}
		// mid ~ e는 모두 정답 후보에서 제외된다.
		else if (vec[mid] > v)
		{
			e = mid - 1;
		}
	}

	cout << ans_idx;

	return 0;
}

 

 

알아둘 것!

이진탐색은

정렬된 배열에서 특정 값이 있는지 확인하는 알고리즘 / 특정값의 인덱스를 찾는 알고리즘이 아니다.

 

위는 이진탐색으로 풀 수 있는 문제의 예시이지.

 

이진탐색은 정답 범위를 관리하면서, 한번에 정답 후보를 절반씩 없애는 행위를 반복하는 것이라고 할 수 있다.

(문제 풀이에서 활용하려면 위처럼 이해하는 것이 좋음)

 

 

 

 

---

 

2.  이진탐색의 응용

다음과 같은 문제가 있다고 하자.

문제)
문자열 S가 주어진다.
S는 계속 'x'가 주어지다가, 어느 순간부터는 계속 'o'가 주어지는 문자열이다.
해당 문자열의 'o' 중에서 가장 왼쪽에 있는 'o'의 인덱스는 무엇인가?

예시)
"xxxxxxxxxxxxxxxxxoooooooo"

답) 16

 

 

위 문제를 풀기 위해 다음과 같이 생각해볼 수 있다.

 

 

위 행위를 코드로 옮겨보자.

 

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

using namespace std;

int main()
{

	string word = "xxxxxxxxxxxxxxxxxoooooooo";

	int s = 0;
	int e = word.length() - 1;
	
	// 답을 담을 변수
	int ans_idx = 0;
	while (s <= e)
	{
		int mid = (s + e) / 2;

		if (word[mid] == 'x')
		{
			s = mid + 1;
		}
		// mid ~ e는 모두 정답 후보에서 제외된다.
		else if (word[mid] == 'o')
		{
			ans_idx = mid;
			e = mid - 1;
		}
	}

	cout << ans_idx;

	return 0;
}

 

 

문제를 풀면서 다시 한번 이해해보자.

 

10815번 : 숫자 카드 (https://www.acmicpc.net/problem/10815) - 기본 이진 탐색 문제.

10815번: 숫자 카드

 

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

using namespace std;

vector<int> vec;

void binary_search(int _x)
{
	// 양 끝점을 정답 범위로 지정한다.
	int s = 0;
	int e = vec.size() - 1;

	// 일단 정답이 없다고 가정
	int ans = 0;

	// 정답 후보가 하나 이상 남아있다면.
	while (s <= e)
	{
		int mid = (s + e) / 2;

		if (vec[mid] == _x)
		{
			ans = 1;
			break;
		}
		// 나와 내 왼쪽은 답이 아니다.
		else if (vec[mid] < _x)
		{
			s = mid + 1;
		}
		// 나와 내 오른쪽은 답이 아니다.
		else if (vec[mid] > _x)
		{
			e = mid - 1;
		}
	}

	cout << ans << " ";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vec.resize(n, 0);
	for (int& ele : vec) cin >> ele;

	// 배열을 오름차순으로 만들기 위해 정렬한다.
	sort(vec.begin(), vec.end());

	int m;
	cin >> m;
	
	int temp;
	for (int i = 0; i < m; i++)
	{
		cin >> temp;
		binary_search(temp);
	}

	return 0;
}

 

 

 

10816번 : 숫자 카드 2 (https://www.acmicpc.net/problem/10816)  - 이진 탐색 응용 문제.

10816번: 숫자 카드 2

 

주어지는 배열을 정렬하여 보면

 

-10 -10 2 3 3 6 7 10 10 10

 

이진 탐색을 이용하면 배열 사이에서 어떤 수의 가장 왼쪽이나 오른쪽의 위치를 찾을 수 있었다.

(위 예제에서는 'o' 중에서 가장 왼쪽 인덱스를 찾았었음.)

 

그렇다면 숫자 카드 2 문제에서 3이 몇개 있는지를 찾는다고 하면

 

2가지 방법이 있다.

 

 

1. 이진탐색 2번 사용

우리는 앞선 이진탐색에서 해당 수의 가장 왼쪽, 오른쪽을 구할 수 있었기 때문에

 

다음과 같이 이진탐색을 2번 진행해서 인덱스들을 구할 수 있다. 

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	vector<int> vec { -10, -10, 2, 3,3, 6, 7, 10, 10, 10 };

	int s = 0;
	int e = vec.size() - 1;

	int idx_left = -1;

	// 3 중에서 가장 왼쪽 찾기
	while (s <= e)
	{
		int mid = (s + e) / 2;
		
		// 3보다 작다면 mid의 왼쪽은 답이 아니다.
		if (vec[mid] < 3)
		{
			s = mid + 1;
		}
		// 3보다 크다면 mid의 오른쪽은 답이 아니다.
		else if (vec[mid] > 3)
		{
			e = mid - 1;
		}
		else
		{
			idx_left = mid;
			e = mid - 1;
		}
	}

	s = 0;
	e = vec.size() - 1;

	int idx_right = -1;
	// 3 중에서 가장 오른쪽 찾기
	while (s <= e)
	{
		int mid = (s + e) / 2;

		// 3보다 작다면 mid의 왼쪽은 답이 아니다.
		if (vec[mid] < 3)
		{
			s = mid + 1;
		}
		// 3보다 크다면 mid의 오른쪽은 답이 아니다.
		else if (vec[mid] > 3)
		{
			e = mid - 1;
		}
		else
		{
			idx_right = mid;
			s = mid + 1;
		}
	}

	cout << idx_right - idx_left + 1;

	return 0;
}

 

 

2. lower_bound, upper_bound

(3을 기준으로 한다면)

lower_bound : 3보다 크거나 같은 것들 중 제일 왼쪽 인덱스를 반환

upper_bound : 3보다 큰 것들 중 제일 왼쪽 인덱스.

 

// -10 -10 2 3 3 6 7 10 10 10
// 위 배열에서 

// lower_bound 3
// -10 -10 2 3 3 6 7 10 10 10
//           v
// 3번 인덱스 반환


// upper_bound 3
// -10 -10 2 3 3 6 7 10 10 10
//               v
// 5번 인덱스 반환

 

 

lower_bound, upper_bound를 구할 줄 안다면 두 값의 차를 이용해 쉽게 3의 개수를 알 수 있다.

(인덱스 차이로 구하면 됨)

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	vector<int> vec { -10, -10, 2, 3, 3, 6, 7, 10, 10, 10 };

	int s = 0;
	int e = vec.size() - 1;

	int lower_bound = -1;

	while (s <= e)
	{
		int mid = (s + e) / 2;

		// 3보다 크거나 같다면.
		if (vec[mid] >= 3)
		{
			lower_bound = mid;
			e = mid - 1;
		}
		else
		{
			s = mid + 1;
		}
	}

	s = 0;
	e = vec.size() - 1;
	int upper_bound = -1;

	while (s <= e)
	{
		int mid = (s + e) / 2;

		// 3보다 크거나 같다면.
		if (vec[mid] > 3)
		{
			e = mid - 1;
		}
		else
		{
			upper_bound = mid;
			s = mid + 1;
		}
	}

	cout << upper_bound - lower_bound + 1;

	return 0;
}

 

 

이진탐색 2번과 근본적인 차이가 있는 것은 아니나

분기를 하나 줄일 수 있고 종종 용어가 사용되기 때문에 알아두면 좋다.

 

 

 

- C++에서 함수를 이용하여 구하기.

c++에서 lower_bound, upper_bound는  <algorithm> 헤더에 함수로 구현되어 있기 때문에 사용해도 된다.

반환값으로는 iterator를 반환하므로 실제 인덱스를 알고 싶다면 배열의 첫번째 iterator를 빼주면 된다.

 

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	vector<int> vec { -10, -10, 2, 3, 3, 6, 7, 10, 10, 10 };

	cout << lower_bound(vec.begin(), vec.end(), 3) - vec.begin();
	// 3 반환
	
	cout << upper_bound(vec.begin(), vec.end(), 3) - vec.begin();
	// 5 반환

	return 0;
}

 

 

 

---

 

3.  매개변수 탐색

다음 문제를 보며 매개변수 탐색이 무엇인지 알아보자.

 

2805번 : 나무 자르기 (https://www.acmicpc.net/problem/2805)

2805번: 나무 자르기

 

// 문제의 예시
4 7
20 15 10 17

 

문제를 해결하기 위해 먼저 완전 탐색부터 접근해보자.

 

위 문제를 완전 탐색으로 푼다면 0부터 최고 높이의 통나무까지 모든 높이로 잘라 문제의 조건에 맞는지 확인해볼 것이다.

0	20 + 15 + 10 + 17 = 62
1	19 + 14 + 9 + 16 = 58
2	18 + 13 + 8 + 15 = 54
3	17 + 12 + 7 + 14 = 50
4	16 + 11 + 6 + 13 = 46
5	15 + 10 + 5 + 12 = 42
6	14 + 9 + 4 + 11 = 38
......
15	5 + 0 + 0 + 2 = 7
16	4 + 0 + 0 + 1 = 5
17	3 + 0 + 0 + 0 = 3

 

기존 문제 => 높이의 최댓값을 구하라.  // 최적화 문제

완전 탐색으로 풀었을 때 => 각 높이를 보면서, 이 높이가 될까?  // 결정 문제

 

[최적화 문제 => 결정 문제]를 매개변수 탐색이라고 부른다.

 

문제를 결정 문제로 바꾼 후, 조건을 다시 읽어보면

 

1. 모든 높이에서 잘라본다 (10억)

2. 이 높이가 답이 되는지 체크해본다 (N번)

 

의 과정을 거쳐야 답이 나온다.

2번만 최적화해서는 답이 제한 시간내에 나오지 못하기 때문에 1번도 최적화를 진행해야하고,

여기서 사용되는 것이 이진 탐색이다.

 

#include <iostream>
#include <limits.h>

using namespace std;

// 해당 높이(mid)가 답이 되는가?
bool check(long long mid);

int main()
{
	long long s = 0;
	long long e = LLONG_MAX;

	long long ans = 0;
	
    // 모든 높이에서 잘라지는가? (이진 탐색을 이용해 최적화)
	while (s <= e)
	{
		long long mid = (s + e) / 2;

		if (check(mid))
		{
			ans = mid;
			s = mid + 1;
		}
		else
		{
			e = mid - 1;
		}
	}

	return 0;
}