바이너리 서치 BinarySearch 이진 탐색 C++ Parametric Search

개요

정렬된 데이터에서 탐색 범위를 반씩 줄여가면서 빠르게 특정값을 찾는 알고리즘

데이터가 주어졌을때 우선 정렬이 된 상태로 만들어 주어야 한다. algorithm을 include하고 sort를 진행한다.

이진 탐색 Flow

1. 탐색 범위에서 시작 지점 index를 left, 종료 지점 index를 right로 지정한다.
2. (left + right) / 2를 통해 left와 right의 중간 index, mid 값을 구해준다.
3. 찾으려는 수와 배열 내에서 mid 인덱스를 가진 수를 비교해 준다.
4. 만약 찾으려는 수가 mid 인덱스를 가진 수보다 작을 경우 mid보다 왼쪽, 클 경우 오른쪽에 있는 것이다.
5. 만약 왼쪽에 있을 경우 left는 그대로 두고 right를 mid로 교체해 준다.
6. 오른쪽에 있을 경우 right는 그대로 두고 left를 mid + 1로 교체해 준다.
7. 2번에서 6번 까지의 작업을 반복하면 원하는 target을 찾을 수 있게 된다.

parametric search

조건에 따라서 범위를 좁혀가면서 답을 구하는 알고리즘 조건에 만족할 경우 일단 정답으로 저장 하고, 더 나은 정답을 찾기 위해 탐색을 계속 해 준다.

좋은 조건을 잘 작성할 경우 문제 풀이의 난이도와 탐색의 기능이 올라간다.

 

예제

1. 특정 숫자 찾기

길이 10개의 배열을 하드코딩하고 배열 내 임의 값을 target으로 설정하여 몇 번만에 해당 숫자를 탐색할 수 있는지 알아보자.

 

코드

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	int arr[10] = { 15, 56, 57, 7, 10, 14, 64, 77, 99, 2727 };
	sort(arr, arr + 10);
	int target = 15, left = 0, right = 9, search = 0, flag = 0;
	while (left < right) {
		search++;
		int mid = (left + right) / 2;
		if (arr[mid] == target) {
			flag = 1;
			break;
		}
		else if (arr[mid] > target) right = mid;
		else left = mid + 1;
	}
	if (flag) cout << search;
	else cout << -1;
}

 

출력

3

 

일반적인 탐색 방법 예를 들어 find를 사용할 경우 최악의 케이스 에서는 target이 배열의 맨 끝에 존재하여 배열 내 모든 범위를 탐색해 주어야 하지만, 이진 탐색을 사용하면 위와 같이 3번만에 target을 찾을 수 있다.

 

실습

1. 특정 수의 제곱근의 정수부 출력하기

제곱근을 구하고 싶은 수 n을 입력 받고 해당 수의 제곱근의 정수부를 출력해 보자

 

코드

#include<iostream>

using namespace std;

long long n;

bool condition(long long num) {
	// 1234567890의 제곱근이 될 수 있는지 검증
	if (num * num > n) return true;
	return false;
}

int main() {
	cin >> n;
	int left = 0;
	int right = 100000000;
	int ret = 0;

	while (left <= right) {
		int mid = (left + right) / 2;
		if (condition(mid)) {
			ret = mid; // 정답을 저장하고, 더 나은 정답을 찾는다.
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << ret - 1;
}

 

입력1

123456789123456

 

출력1

11111111

 

입력2

9585848572838475

 

출력2

97907346