자료의 탐색 - 이진 탐색(Binary search)

이진 탐색(Binary search)

가운데에 있는 항목을 키값과 비교하여 다음 탐색 위치를 결정하여 키를 찾을 때까지 이진 탐색을 반복적으로 수행한다.

 

ex) 순차 탐색과 달리 묶음 책 속의 수들이 차례대로 정렬되어 있는 구조를 가졌다는 전제를 토대로 책의 중간에 위치한 수를 먼저 비교하고 찾고자 하는 수가 비교한 수보다 큰 경우는 책의 오른쪽 부분을 탐색하고 작은 경우는 책의 왼쪽 부분을 탐색하는 것을 반복하는 방법.
  - 찾는 키값 > 원소의 키값: 오른쪽 부분에 대해서 이진 탐색 실행
  - 찾는 키값 < 원소의 키값: 왼쪽 부분에 대해서 이진 탐색 실행

이진탐색(Binary search) 탐색방법

 ① 자료의 집합에서 n/2 번째 원소를 키값과 일치하는지 비교한다.

 ② 찾는 키값이 원소의 키값보다 크면 (n/2)+1 번째에서 n 번째 부분에 대해 이진 탐색 수행
      찾는 키값이 원소의 키값보다 작으면 1번째에서 (n-1)/2 번째 부분에 대해 이진 탐색 수행

 ③ 위 ② 과정에서 찾는 키와 일치하면 그 원소를 반환

 ④ 만일 ①, ② 과정의 반복 이후에도 키값이 일치하는 원소가 없으면 찾는 원소가 없는 것으로 판단

이진탐색(Binary search) 의사코드

search_binary(list, low, high)    middle ← low에서 high사이의 중간 위치    if (탐색값 ≠ list[middle]) return TRUE;    else if (탐색값 < list[middle])       return list[0]부터 list[middle-1]에서의 탐색;    else if (탐색값 > list[middle] )       return list[middle+1]부터 list[high]에서의 탐색;

이진 탐색의 탐색 과정

이진탐색(Binary search) 예제

문제: 10장으로 구성된 묶음 책으로 각 장에 수가 다음과 같이 임의로 배치되어 있다.

1)찾고자 하는 수가 78인 경우

2)찾고자 하는 수가 34인 경우

이진탐색(Binary search) 비교횟수, 특징

비교횟수

   -최선의 경우 ⇒ 1

   -최대 비교 횟수 ⇒ log2^n +1   n/2, n/4, n/8, ...

   -탐색의 평균 비교 횟수 ⇒ (log2 n +1) / 2

   -시간복잡도 ⇒ O(long N)

특징

   -자료가 정렬되어 있어야 한다.

   -자료가 커지면 커질수록 탐색할 때 효율적이다.

   -탐색 알고리즘은 복잡하나 속도가 빠르다.