알고리즘-이분검색

이분검색은 구간의 중간값과 키값의 대소를 구분하여 테이블을 절반씩 나눠가며 비교하는 방식이다.

한번 비교할 때마다 테이블의 길이가 절반씩 줄어들기 떄문에 검색 효율은 상당히 좋은 편이며 테이블이 커도 속도가 느려지지 않는다.

 

일반적으로 우리가 영한 사전을 검색할 때 이분검색을 사용한다.

이분 검색이 가능하려면 테이블의 모든 자료가 오름차순으로 정렬되어 있어야 한다는 조건이 있다.

 

이분검색이 속도가 바르다.

장점: 테이블이 아무리커도 비교횟수가 적다.