21.3 검색 알고리즘의 분석

검색은 컬렉션과 대상 항목을 받아서 대상이 컬렉션에 있는지를 판단하고, 때로는 대상의 인덱스를 반환하는 알고리즘이다.

가장 간단한 검색 알고리즘은 “선형 검색”인데, 컬렉션의 항목을 순서대로 순회하면서 대상을 발견하면 중단하는 것이다. 선형 검색은 최악의 경우에 전체 컬렉션을 순회하며, 실행 시간은 선형이다.

시퀀스의 in 연산자는 선형 검색을 사용한다. find, count 같은 문자열 메서드로 선형 검색을 사용한다.

시퀀스의 원소가 정렬되어 있다면 이분 검색(bisection search)을 사용할 수 있다. 이분 검색은 O(log n)이다. 이분 검색은 사전(종이 사전, 자료 구조 아님)에서 단어를 찾을 때 사용하는 알고리즘과 비슷하다. 처음부터 시작하는 대신 각 항목이 정렬되어 있는지 확인하고, 중간에 있는 항목부터 시작해서 찾으려는 단어가 앞 또는 뒤에 있는지 확인하는 것이다. 앞에 있다면 시퀀스의 앞부분 절반을 검색하면 된다. 뒤에 있다면 시퀀스의 나머지 절반을 검색하면 된다. 어느 쪽이든 남은 항목 수가 절반으로 줄어든다.