이진 탐색(Binary Search), 시간 복잡도 O(log N)

2진 탐색

인덱스가 0부터 16까지 있는 array가 있을 때 

그 중 정답이 target인 값을 찾으려면 어떻게 해야할까?

 

for문을 통해 처음부터 하나씩 비교하는 방법이 있겠지만

맨 마지막에 정답이 있으면 O(N) 만큼의 시간 복잡도가 걸리게 될 것이다. 

 

이 때, 2진 탐색이라는 방법을 통해 시도 횟수를 확 낮출 수 있다.

딱 가운데 위치하는 값을 정답과 비교해서 정답이 더 크다면

가운데 위치하는 값 이하의 인덱스를 모두 버리고

정답이 더 작다면

가운데 위치하는 값 이상의 인덱스를 모두 버리는 식으로 구하며 이를 반복하면 된다. 

이는 알고리즘 문제에서 UP & DOWN 문제로도 자주 나오는 형태이다. 문제풀이 예시

 

시간 복잡도 O(log N)

총 숫자가 1 ~ N 까지라고 한다면

1번 탐색하면 반절이 줄어드니 N/2개가 남는다.

2번 탐색하면 반절이 또 줄어드니 N/4 = N/2²개가 남는다.

3번 탐색하면 반절이 또 줄어드니 N/8 = N/2³개가 남는다.

...

K번 탐색하면 반절이 또 줄어드니 N/2^k개가 남는다.

 

이 때, 이진 탐색을 통해 남은게 딱 1개라고 가정해보자

이걸 수식으로 표현하면 N/2^k = 1 이다. 

즉, k = log₂N 횟수를 시도하면 정답을 찾을 수 있는 것이다. 

 

정리

1. 결론적으로 이진 탐색을 위해서는 시간 복잡도가 O(log N) 만큼 걸린다고 볼 수 있겠다. (상수는 버리고)
   헷갈린다면 연산량이 반으로 나눠진다 싶을 때 시간 복잡도가 O(log N)이겠구나 라고 생각하면 된다. 
2. 이진 탐색은 일정한 규칙으로 정렬되어 있는 데이터일 때만 사용이 가능하다.
   이진 탐색을 위해선 정렬이 필요한데 정렬에 대해서는 따로 포스팅할 예정이다.