[알고리즘] 이진탐색

이진탐색 

 

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

 

 

 

 

전체 범위에서 4를 찾고 싶기 때문에 시작점은 [0], 끝점은 [9]로 설정하며 중간값은 [4]로 설정한다.
0과 9의 중간값은 4.5 이지만 소수점 이하를 제거하여 [4]로 중간값을 설정한 것이다.
 

 

중간점 [4]를 기준으로 오른쪽에 있는 값들은 볼필요 없기 때문에 끝점을 중간점의 왼쪽으로 옮긴다.

그후 중간점은 인덱스[1], 즉 숫자 2이며 우리가 찾고자하는 값 4가 아니다. 2보다 우리가 찾고자 하는 값인 4가 더 크기 때문에 중간점을 기준으로 왼쪽에 있는 값들은 볼 필요가 없게 된다. 따라서 이번에는 시작점 위치를 중간점 오른쪽으로 옮긴다.

 

 

시작점[2], 끝점[3]으로 설정했을 때 중간점은 [2]이며 중간점[2]에 위치해있는 숫자 4는 우리가 찾고자 하는 값이므로 탐색을 마친다.

이진탐색의 시간 복잡도는 
1. 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례한다.
2. 예를들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남는다.
 - 2단계를 거치면 8개 가량의 데이터만 남는다.
 - 3단계를 거치면 4개 가량의 데이터만 남는다.
3. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다.

 

https://youtu.be/94RC-DsGMLo