“Chapter 11의 탐색은 Chapter 08 에서 소개한 트리의 뒷이야기에 해당합니다.”
굳이 따지자면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다.
“효율적인 탐색을위해서는 ‘어떻게 찾을까’만을 고민해서는 안 된다. 그보다는 ‘효율적인 탐색을 위한 저장방법이 무엇일까’를 우선 고민해야 한다.”
그런데 효울적인 탐색이 가능한 대표적인 저장방법은 ‘트리’이다. 때문에 지금부터 시작할 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다.
보간 탐색은 그 값이 상대적으로 앞에 위치한다고 판단을 하면 앞쪽에서 탐색을 진행한다. 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의인덱스 값이 비례한다고 가정하기때문에, 위 그림을 근거로 다음의 비례식을 구성한다.
A = arr[high] - arr[low]
Q = arr[s] - arr[low]
A:Q = (high - low) : (s - low)
s = Q/A(high - low) + low
“사번이 7인 직원의 정보를 찾아야지!”
탐색키는 고유해야 합니다.”