[ch 11-1] 탐색의 이해와 보간 탐색

[주제]

- 보간 탐색의 개념

[정의]

- 이진 탐색의 비효율성을 개선시킨 알고리즘

[중요]

- 효율적인 탐색을 위해서는 '어떻게 찾을까'가 아닌, 효율적인 탐색을 위한 '저장방법'이 무엇인지를 우선 고민해야 함

- 탐색 대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작

  ※ 예) 고길동이라는 사람의 전화번호를 찾을 때, 전화번호부의 인덱스를 보고 'ㄱ'에 해당하는 앞쪽에서 찾기

■ 그림(보간 탐색)

- 보간 탐색은 찾아야 하는 값이 상대적으로 앞에 위치한다고 판단하면 앞쪽에 탐색

- low: 탐색 대상의 '시작' 인덱스 값

- high: 탐색 대상의 '끝' 인덱스 값

- S: 찾는 데이터가 저장된 위치의 인덱스 값

- 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정

■ 1차 공식

 A : Q = (high - low) : (S - low)

■ 2차 공식

■ 3차 공식

- 찾는 데이터의 값 'arr[S]를 x'라 할 때 최종 공식

- 오차율을 최소화하기 위해 정수형 나눗셈이 아닌 실수형 나눗셈으로 진행