개발일지

소프트웨어 20, 10억 개 전화번호에서 이름찾기 : 이진검색 선형 알고리즘보다 더 나은 방법은 없을까? 이름과 전화번호가 적힌 리스트나 명함 다발이 많이 있다고 가정해보자. 이름이 순서없이 섞여 있는 상태에서 '마이크 스미스'의 전화번호를 찾으려 한다면, 그 이름을 찾을 때까지 리스트를 전부 확인해야 할 것이고 아예 그 이름을 찾지 못할 수도 있다. 하지만 이름이 알파벳순으로 되어 있다면 더 쉽게 찾을 수 있다. 종이 전화번호부에서 이름을 찾는 방법을 생각해보자. 중간 페이지부터 반을 갈라 알파벳순으로 보며 해당 알파벳을 찾으면 절반 관계없는 페이지는 무시하고 점점 범위를 좁히며 찾게된다. 노래방 책 또한 같다. 이 검색 알고리즘을 이진 검색(binary search)이라고 한다. 이는 분할 정복(di..