이분 탐색(Binary Search)
데이터가 담긴 리스트를 탐색하는 방법은 크게 순차 탐색(Linear Search)과 이분 탐색(Binary Search)이 존재한다. 예를 들어 { 8, 3, 1, 5, 4, 7, 9, 2, 6, 10}, 10개의 데이터가 담긴 리스트가 있다고 하자. 이 리스트에서 9의 위치를 찾기 위해서는 어떻게 해야 할까? 위 리스트처럼 정렬되지 않은 리스트에서 데이터를 탐색하기 위해서는 어쩔 수 없이 처음부터 끝까지 순차적으로 탐색을 진행하여 9의 위치를 찾는 방법밖에 없을 것이다. 그렇다면 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}처럼 정렬된 리스트가 있다고 생각해 보자. 이 리스트에서도 9의 위치를 찾기 위해서는 어떻게 해야 할까? 단순하게는 앞서 언급한 방법처럼 처음부터 순차적으로 9의 인덱스..
2021. 7. 2.
