binary search ; 이진검색

이진검색은 정렬된 연속 리스트 내에서 어떤 항목을 빠르게 찾기 위한 기법이다. 즉, 찾고자하는 가 리스트의 앞이나 끝에서부터 순차적으로 비교되는 것이 아니라, 가운데에 위치해 있는 항목과 비교된다. 그런 다음 가운데에 있는 값과의 비교 결과에 따라 다음의 세 가지 중 하나를 선택한다.

  • 만약 찾고자 하는 키가 비교 대상보다 작으면서, 검색해야할 데이터가 더 남아있다면, 비교대상보다 작은 쪽에 남아있는 절반의 부분에 대해 이진검색을 계속 수행한다.
  • 만약 찾고자 하는 키가 비교 대상과 같다면, 바로 그 비교 대상이 찾으려는 값이므로 검색을 중단한다.
  • 만약 찾고자 하는 키가 비교 대상보다 크면서, 검색해야할 데이터가 더 남아있다면, 비교대상 보다 큰 쪽에 남아 있는 절반의 부분에 대해 이진검색을 계속 수행한다.

이진검색은 키가 찾아지거나, 차례로 검색될 잔여 그룹이 아주 작아질 때까지, 그 데이터를 포함하고 있는 절반의 리스트 중에서 다시 가운데 있는 항목의 값과 비교하는 일이 계속된다.


이 정보는 2000년 6월 10일에 수정되었습니다.
영어판(whatis.com)