이분탐색

이분탐색은 어떤 경우의 수를 하기에는 조금 애매하거나 n이 무지막지하게 큰 경우 O(logN) 만에 처리해야 겠다는 생각이 들 경우 시도를 해보는 알고리즘이다.

정렬된 배열에 특정원소가 있는지를 확인하는 것을 logN만에 해결하는 알고리즘

정렬된 배열의 가운데를 살펴보고 찾고자 하는 원소가 그 안에 있는지를 확인한다.

만일 그 안에 있다면 멈춘다.

그 외에는 왼쪽에 있는지 오른쪽에 있는지를 판단하여 탐색을 진행한다. 할 때마다 절반으로 줄어들기 때문에 이 알고리즘의 복잡도는 logN이다.

예시문제

2776번: 암기왕

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며,

www.acmicpc.net

예시 문제

2792번: 보석 상자

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하

www.acmicpc.net

이분탐색은 최적화 문제를 결정문제로 바꾸기도 한다.

선형적으로 탐색하기에는 너무 큰 선형 복잡도를 가진 경우에는 이분 탐색을 생각한다.

sangyunpark99