범위를 반씩 좁혀가는 탐색

순차 탐색 이번 장에서는 리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘에 대해서 공부하겠다. 이진 탐색에 대해 알아보기 전에 가장 기본적인 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다. 1장부터 차례대로 읽은 독자라면 이미 자연스럽게 순차 탐색의 원리를 익혔다. 사실 지금까지 예제 문제에서 N개의 데이터가 있을 때, 그 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해준 경우가 많았는데 그 자체로도 이미 순차 탐색이라고 할 수 있다. 예를 들어 3장의 '거스름돈'문제에서 가장 큰 화폐단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것을 기억해보자. 이와 같이 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하..