[Algorithm] 이진탐색

 

이진탐색이란?

리스트나 트리에서 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀 나가는 탐색방식

 

이진 탐색 방식

1. 리스트의 가운데 값을 찾아 찾는 값과 비교.

2. 가운데 값이 찾는 값보다 크면 가운데 값을 기준으로 왼쪽 영역으로 가서 탐색

    작으면 가운데 값을 기준으로 오른쪽 영역에 가서 탐색

3. 찾는 값이 나올때 까지 반복.

 

이진 탐색 방식 예시

1. 12를 찾는다고 가정하였을때 위 배열에서 중간값은 8이다. 12가 8보다 크므로 8기준 오른쪽 영역을 탐색한다.

2. 오른쪽 영역에서 중간값은 14이다. 12가 14보다 작으므로 14기준 왼쪽 영역을 탐색한다.

3. 왼쪽 영역에서 중간값은 11이다. 12가 11보다 보다 크므로 11기준 오른쪽 영역을 탐색한다.

4. 오른쪽 영역의 중간값은 12인데 찾는 값 12와 동일하므로 탐색을 종료한다.

 

이진 탐색의 시간복잡도

O(logn) 

한 번 탐색할 때 마다 탐색하고자 하는 범위가 절반씩 줄어들기 때문