1일상생활 속의 탐색 문제

 

사람들은 일상생활 속에서 알게 모르게 굉장히 많은 탐색 문제를 풀면서 살아갑니다.

첫 번째 예로 두꺼운 책을 한 권 앞에 두고 특정한 쪽 수(예를 들어 618쪽)를 찾는 과정을 떠올려 봅시다.

 

1 | 우선 책의 중간쯤을 펼쳐 쪽 수를 보니 520쪽입니다.

2 | 찾고자 하는 쪽 수가 펼친 쪽 수보다 크므로(618 > 520) 펼친 곳의 앞쪽은 더 이상 찾을 필요가 없습니다.

3 | 현재 펼친 곳에서 뒤쪽으로 적당해 보이는 곳을 다시 펼치니 710쪽입니다.

4 | 찾고자 하는 쪽 수가 펼친 쪽 수보다 작으므로(618 < 710) 펼친 곳의 뒤쪽은 더 이상 찾을 필요가 없습니다.

5 | 이번에는 다시 앞쪽으로 책을 펼쳤더니 613쪽이 나옵니다.

6 | 찾으려는 쪽 수와 가까운 쪽까지 왔으니 이제 쪽을 한 장 한 장 뒤로 넘깁니다.

7 | 원하는 618쪽이 나오면 탐색을 멈춥니다.

 

그림 12-1 책에서 원하는 쪽을 찾는 과정