binary search – 이진검색

이진검색은 정렬된 연속 리스트 내에서 어떤 항목을 빠르게 찾기 위한 기법이다.

즉, 찾고자하는 키가 리스트의 앞이나 끝에서부터 순차적으로 비교되는 것이 아니라, 가운데에 위치해 있는 항목과 비교된다.

그런 다음 가운데에 있는 값과의 비교 결과에 따라 다음의 세 가지 중 하나를 선택한다.

만약 찾고자 하는 키가 비교 대상보다 작으면서, 검색해야할 데이터가 더 남아있다면, 비교대상보다 작은 쪽에 남아있는 절반의 부분에 대해 이진검색을 계속 수행한다.

만약 찾고자 하는 키가 비교 대상과 같다면, 바로 그 비교 대상이 찾으려는 값이므로 검색을 중단한다.

만약 찾고자 하는 키가 비교 대상보다 크면서, 검색해야할 데이터가 더 남아있다면, 비교대상 보다 큰 쪽에 남아 있는 절반의 부분에 대해 이진검색을 계속 수행한다.

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