12-1 (탐색 알고리즘)

순차탐색: 정렬되지 않은 테이블에서도 원하는 레코드를 찾을 수 있는 가장 단순하고 직관적인 방법.

테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾음.

탐색함수는 탐색 대상인 리스트 A와 탐색 키, 리스트에서 탐색 범위 low, high를 매개변수로 전달받음.

리스트의 low 위치부터 탐색을 시작하여, 탐색이 성곡하면 항목의 위치를 반환함. 만약 high까지도 원하는 레코드가 나타나지 않으면 None을 반환한다.

탐색의 성능은 최선의 경우 찾는 항목이 맨 앞에 있는 경우고, 맨 뒤에 있거나 리스트에 없는 키를 찾는 경우 최악이다.

그러므로 평균 비교 횟수는 (1+2+3+...+n)/n=(n+1)/2 다. => 시간 복잡도는 O(n)

 

이진탐색: 테이블의 중앙에 있는 값을 조사하여 찾는 항목이 왼쪽에 있는지 오른쪽에 있는지를 판단함.

만약 찾는 항목이 왼쪽에 있다면, 오른쪽을 탐색할 필요학 없어지고 검사해야 할 항목수가 반으로 줄어든다.

일상생활에서는 사전에서 단어를 찾는 과정에서 사용된다.

각 단계에서 탐색 범위가 반으로 줄어들어 탐색 범위가 1이 될 때의 탐색 횟수를 k라 하면, n/(2^k)=1이 된다. 즉, k=log2(n)이므로 시간 복잡도는 O(log2(n))이다.

이진 탐색은 매우 효율적인 탐색 방법이지만 탐색하기 전에 반드시 배열이 정렬되어 있어야 한다는 전제조건이 있어 데이터의 삽입/삭제가 빈번한 응용에서는 적절치 않음.

 

보간탐색: 이진탐색의 일종으로 우리가 사전에서 단어를 찾을 떄와 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법.

ex) 'ㅎ'로 시작하는 단어는 사전의 뒷부분에서 찾고 'ㄱ'으로 시작하는 단어는 앞 부분에서 찾는 것과 같은 원리임.

시작복잡도의 경우 이진 탐색과 같은 O(log2(n))지만 많은 데이터가 비교적 균등하게 분포되어 있는 자료의 경우 훨씬 효율적인 방법이다.