[ALGORITHM] 이진 탐색(Binary Search)

이진 탐색(Binary Search)은 정렬된 데이터를 이분화하며 탐색하는 방법이다.

탐색하는 범위를 절반씩 줄여가며 원하는 데이터를 찾아간다.

 

즉, 순서대로 정렬된 데이터에서 탐색 범위를 반으로 나누어 중간에 위치한 데이터와 찾고자 하는 데이터를 비교한다.

그리고 원하는 데이터와 근접한 부분을 다시 탐색 범위로 지정하여 반복해 나간다.

 

 

   1. 정렬된 데이터에서 찾고자 하는 데이터를 정한다.

 

▲ 찾을 데이터 지정

 

   2. 중간에 위치한 데이터 '7'과 찾고자 하는 데이터 '9'를 비교하여 준다.

 

▲ 중간 데이터와 찾을 데이터 비교

 

   3. '9'는 중간 데이터인 '7'보다 크기 때문에 탐색 범위를 '7'보다 크게 잡아준다.

 

▲ 탐색 범위 재 지정

 

   4. 다시 지정한 탐색범위(8~9)에서 중간에 위치한 데이터인 '9'와 찾고자 하는 데이터가 일치하여 탐색을 종료한다.

 

▲ 탐색 종료