[CS50] 알고리즘 - 검색 알고리즘

검색 알고리즘

메모리 구조, 자료형, 배열과 같은 기본 개념을 활용하여 검색과 정렬 문제를 푸는 알고리즘을 배워보자.

 

주어진 배열에서 특정 값을 찾는 방법부터 알아보자.

 

배열은 한 자료형의 여러 값이 메모리상에 모여 있는 구조다. 컴퓨터는 배열의 인덱스를 하나씩 접근한다.
어떤 값이 배열 안에 있는지 찾으려면 배열이 정렬되어 있는지에 따라 다른 방법을 사용한다.

선형 검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 값을 검사한다.

For i from 0 to n–1
        If i'th element is 50
                Return true
Return false

• 모든 원소를 순서대로 확인하므로 정렬 여부와 관계없이 사용할 수 있다.
• 시간 복잡도: O(n)

 

이진 검색

배열이 정렬되어 있다면 더 효율적인 방법을 사용할 수 있다.

 

배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교한다. 그보다 작으면 왼쪽 절반, 크면 오른쪽 절반을 탐색한다.

If no items
        Return false
If middle item is 50
        Return true
Else if 50 < middle item
        Search left half
Else if 50 > middle item
        Search right half

• 매번 탐색 범위를 절반으로 줄이므로 훨씬 빠르다.
• 시간 복잡도: O(log n)

주의: 이진 검색은 정렬된 배열에서만 정확하게 동작한다.

 

연습 문제

Q. 정렬되지 않은 배열이 있다면, 선형 검색과 이진 검색 중 어느 것이 빠를까?
선형 검색이 적합하다.
정렬되지 않은 배열에서 이진 검색은 정확하지 않다. 이진 검색은 배열이 정렬되어 있다는 전제하에 중간 값과 비교하여 절반씩 탐색 범위를 줄인다.

 

정렬되지 않은 배열에서는:

• 운에 따라 빠를 수도 있음
• 값이 있는데도 찾지 못할 수 있음
• 잘못된 결과 반환 가능

따라서 정렬되지 않은 배열을 정확하게 검색하려면 선형 검색을 사용해야 한다.

 

요약
정렬된 배열 → 이진 검색 (빠름)
정렬되지 않은 배열 → 선형 검색 (정확함)