CH11-1 탐색의 이해와 보간 탐색(1)
정렬을 공부했으니 탐색을 공부할 차례라는걸 생각할 수 있다.
기존 정렬 공부에서는 정렬하는 방법만을 공부했음. 이번 탐색에서는 탐색하는 방법을 공부할 것 같다. 하지만 사실 11과 12챕터에서 핵심 이슈는 탐색을 잘하기 위한 자료구조, 즉 탐색을 잘하기 위한 데이터의 저장방법이 무엇인가를 고민하는 것임.
탐색이 아무리 좋은 알고리즘이어도, 데이터가 중구난방으로 저장되어있으면 탐색 알고리즘이 성능이 최대화되지 않는다. 한계가 있음 따라서 우리는 앞으로 탐색을 위한 좋은 데이터 저장방법이 무엇인가를 고민하는 것이다.
탐색은 사실 앞서 우리가 배운 이진트리의 연장선상이다. 왜냐하면 이진트리가 탐색을 위한 좋은 자료구조이기 때문이다.
그래도 탐색이기 때문에… 소개하는 관점에서 탐색알고리즘을 하나 알려주겠다.
사실 탐색하면 제일먼저 떠오르는게 이진탐색일 것이다. 그런다고 이진탐색만 소개하고 책을 마치면 아쉽기 때문에 보간탐색이란걸 하나 소개해주려고 한다.
그럼 보간 탐색이 무엇인가?
이진탐색은 가장 가운데 인덱스를 찾는 것 부터 시작한다. 이진탐색은 탐색을 위한 루틴이 진행될때마다 탐색대상이 되는 데이터의 수가 반씩 줄어들어서 성능이 좋다고 평가했다.
그런데 보간탐색은 다르다.
만약 내가 찾고자하는 데이터가 11이면? 이는 왼쪽에 치우친 데이터이다. 이진탐색에서는 이런 치우침을 고려하지 않고 무조건 가운데부터 탐색한다.