#6-2-1 The Art of Computer Programming - 정렬과 검색

이번 절은 키 비교에 의한 검색에 대한 내용이다.

그중에서도 정렬된 표의 검색에 대해 알아본다.

 

어떤 표를 검색할 때, 딱 한 번만 검색한다면 순차 검색을 사용하는 게 더 빠를 수도 있다.

하지만 여러 번 자주 검색한다면 미리 정렬 후 검색하는게 이득이다.

 

정렬되어 있는 데이터에서 가장 간단하고 효율적으로 검색 할 수 있는 방법은 이진 검색이다.

중간위치의중간 위치의 값을 확인하고 그것보다 작으면 왼쪽, 크면 오른쪽을 선택해서 또 중간 위치의 값을 확인하는 식의 반복이다.

 

의사결정 트리를 활용하는 방법도 있다.

트리의 형태가 조금은 다른 균등 이진 트리를 활용하는 방법도 소개한다.

 

피보나치식 검색 : 피보나치 수들이 2의 거듭제곱등과 비슷한 역할이 가능하므로 활용할 수 있음.

 

보간 검색 : 사람들이 실제로 검색할 때는 2진 트리 등을 사용하는게 아니라 앞부분부터 찾거나 인덱스를 보고 찾아가는 식의 방법을 차용한다. 그리고 내가 찾고자 하는 값보다 너무 클 경우 왼쪽을 많이 내려가서 찾고, 너무 작을 경우 오른쪽을 많이 올라가서 찾는 등의 가중치가 존재한다. 그리고 사람이 사전에서 단어를 찾는 것은 내부 검색이 아니라 외부 검색 개념이라고 한다.