이진 탐색(Binary Search)란?

알고리즘 문제를 풀다 보면, 배열과 같은 list에서 특정 값을 구하는 문제를 자주 발견할 수 있다.

이러한 여러 데이터들이 있는 list에서 한 데이터를 Search하는 과정은 크게 두가지가 있다.

 

 

1. 순차 탐색(linear search): list의 데이터를 순차적으로 찾는 방식. ( 시간 복잡도: O(n) )

2. 이진 탐색(binary search): list의 데이터를 반씩 나누며 찾는 방식. ( 시간 복잡도: O(log n) ) 

 * 단, 반드시 정렬된 상태에서 탐색해야 한다.

 

가장 단순해 보이는 순차 탐색을 매번 사용하면 좋겠지만, 알고리즘 문제를 순차 탐색으로 풀다 보면 시간 초과가 나는 경우가 대다수이다.

그렇다면 이진 탐색에 대해 더 알아보도록 하겠다.

 

이진 탐색이란?

정렬된 데이터가 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

전체 배열 중 중간 값을 시작으로, 반씩 범위를 좁혀 찾아가는 방식이다.

시간 복잡도는 O(log n)이다.

 

 

 

 

 

 

이진 탐색의 구현 원리

 

 

 

 

 

이진 탐색 시간 복잡도

 

이진 탐색의 최악의 경우는 탐색 대상의 범위가 한 개만 남았을 때이다.

1~8의 리스트에서 1이 되기까지 2로 나눈 횟수는 현재 갯수의 반씩 계속 줄어드니까

이러한 계산식이 성립된다.

이진 탐색으로 탐색할 갯수가 한 개가 남은 상황이고, 나머지 하나까지 탐색하는 식은 

이지만 +1 은 생략이 가능하여, 

log n이 된다.

 

 

 

 

 

 

 

이진 탐색(Binary Search)의 구현 방식

 

1. 반복문 구현

 

 

2. 재귀적 구현

 

 

 

왜 start > end가 종료 조건이 되는 걸까?

e가 -1 되어 더 작아질 때

s가 +1 되어 더 커질 때

직접 정렬된 배열에 없는 데이터를 이진 탐색 통해 구하는 과정을 써보았다.

 

그 결과

1. 어떤 과정을 거치던 마지막 전에 s와 e의 값이 같아진다.

2. 그때의 mid값이 target보다 작으면 s+1되어 e 보다 커진다. 혹은 mid 값이 target보다 크다면 e가 -1되어

e가 s값 보다 작아진다.