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

1. 개요

1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘

 

2. 알고리즘 코드

vector<int> ans;

// 이진 탐색 알고리즘
int binary_search(int n)
{
	int low = 0;
	int high = ans.size() - 1;
	int ret = MAX_N;

	while (low <= high) {
		int mid = (low + high) / 2;
		int num = ans[mid];

		if (num >= n) {
			ret = min(ret, mid);
			high = mid - 1;
		}
		else
			low = mid + 1;
	}

	return ret;
}

 

3. 문제

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

12015번: 가장 긴 증가하는 부분 수열 2

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