이진 탐색 Binary Search

이진 탐색 Binary Search

 

이진 탐색은 한번 비교를 할 때마다 탐색 범위가 절반으로 줄어든다.

 

정렬된 배열을 전제로 탐색한다. 

 

1

3

5

7

9

11

13

위와 같은 정렬된 배열에서 Binary Search 이진 탐색을 적용하여 9 를 탐색하는 경우를 생각할 수 있다.

 

1. 정렬된 배열의 중앙 요소를 선택한다.

   • < 7 선택 >

2. 선택된 값과 찾고자 하는 값을 비교하여 왼쪽 혹은 오른쪽 중 어느 방향으로 탐색을 진행할지를 정한다.

   • < 7이 9보다 작기 때문에 7을 기준으로 오른쪽의 값들을 탐색한다. >

3. 위의 과정을 반복한다.

   • < 11 선택 >

   • < 11이 9보다 크기 때문에 11을 기준으로 왼쪽의 값들을 탐색한다. >

4. 남은 탐색 값은 9가 남고, 찾고자 하는 값과 일치하므로 탐색을 끝마친다.

 

 

 

 

이진 탐색 성능

데이터 집합의 크기 n

반복 횟수 k

 

데이터 집합의 크기 n 을 2로 몇 번 나누어야 1이 되는지, 해당 k값을 확인할 수 있다. 

 

 

 

 

탐색 과정

탐색하고자 하는 범위를 정의하기 위해 변수 left와 right, mid를 사용한다.

처음에 left는 0, right는 last index, mid는 ( left + right ) / 2 로 설정한다.

 

right < left가 되는 순간 탐색이 종료되며, 그 전에 해당 값을 찾으면 종료된다.

 

mid값과 찾고자 하는 값 answer 을 비교하여

mid < answer 이면 left = mid + 1

answer < mid 이면 right = mid - 1