이분탐색

 'N개의 배열안에 특정 M이라는 숫자가 존재하는지 알아내라' 라는 문제를 처음 봤을 때,

단순히 "배열 인덱스를 하나씩 증가하면서 탐색하라는 거 아닌가?" 라고 생각할 수 있다.

하지만, 백준 1920 번 문제 https://www.acmicpc.net/problem/1920  와 같이 찾고자 하는 수의 범위가 크고,

배열의 크기 또한 큰 경우 시간초과가 날 수 있다. 이 경우 쿼리가 M개, 배열이 최대 N개 이기 때문에 O(NM) 이 발생하여 시간초과.

즉 다른 방법을 찾아보아야 한다. 이때, 방법을 절반을 나누어가면서(이등분) 탐색하는 건..? 이라는 접근을 통해 풀이해볼 수 있으며,

방법은 다음과 같다.

 1) 배열을 우선 오름차순으로 정렬한다.

 2) 현재 배열의 중심(MIDDLE) 을 파악한다.

 3) 중심에 있는 값보다 현재 찾고자 하는 값이 작은경우 LEFT ~ MIDDLE-1 을 탐색한다.

                                                            큰경우   MIDDLE+1 ~ RIGHT 를 탐색

                                                            같은경우 출력하고 종료!

예제는 그림으로 나타내보았다 :)

의외로 간단하고 탐색의 기본이라 할 수 있기에 소스코드를 보고 이해해보도록 하자 

<소스코드>

#include <cstdio>

void find(int num) {
	flag = false;
	int left = 0, right = N - 1, mid = (left + right) / 2;
	while (left <= right) {
		if (A[mid] == num) {
			break;
		}
		else if (A[mid] < num) {
			left = mid + 1;
		}
		else if (A[mid] > num) {
			right = mid - 1;
		}
		mid = (left + right) / 2;
	}
}