탐색 (검색) 알고리즘 : 선형 (순차) 탐색 (Linear/sequential), 이진 탐색 (Binary search) 비교, 차이점

탐색 (검색) 알고리즘은 데이터 구조 내에서 특정 항목이나 값을 찾는 프로세스를 자동화하는 알고리즘이다. 이 알고리즘은 컴퓨터 과학과 정보 기술에서 중요한 역할을 한다. 데이터가 저장된 컬렉션(배열, 리스트, 트리, 그래프, 데이터베이스 등)에서 특정 값을 찾는 작업은 다양한 응용 프로그램에서 중요하며, 이를 효율적으로 수행하는 알고리즘을 개발하는 것은 매우 중요하다.

 

탐색 알고리즘에는 선형 탐색, 이진 탐색, 해시 테이블, 이진 탐색 트리, 그래프 탐색 알고리즘, 문자열 검색 알고리즘 등이 일반적으로 사용된다. 그 중 가장 대표적인 선형 탐색과 이진 탐색에 대해 알아보고, 차이점을 비교해보도록 하겠다.

 

1. 선형 탐색 알고리즘 (순차 탐색 알고리즘) Linear (Sequential) serarch algorithm
2. 이진 탐색 알고리즘 Binary search algorithm
3. 선형 탐색, 이진 탐색 비교

 

---

 

선형 탐색 (순차 탐색) Linear (Sequential) serarch 

순차적으로 모든 원소를 탐색하여 원하는 값을 찾아내는 방법이다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우엔 배열에 있는 모든 원소를 전부 검사해야 할 수 있다.

 

 

---

 

이진 탐색 Binary search 

탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용할 수 있다. 배열의 가운데 원소와 찾으려 하는 값을 비교하면, 왼쪽이나 오른쪽 어디에 있을 지를 알 수 있다. 쉽게 말하면, 크기 순으로 정렬되어 있는 정렬을 반씩 제외하며 탐색하는 방법이다.

 

 

(예제) 이진 탐색 알고리즘 구현

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수를 구현하라. 단, 효율성 평가도 진행하므로 선형 탐색 알고리즘으로 구현할 경우 부적절할 수도 있다.

# 이진 탐색
def solution(L, x):
    lower = 0
    upper = len(L) - 1

    while lower <= upper : 
        middle = (lower + upper) // 2
        if L[middle] == x : 
            return middle
        elif L[middle] < x : 
            lower = middle + 1
        else :
            upper = middle - 1
    return -1

# 선형 탐색
def solution(L, x):
    return L.index(x) if x in L else -1

이처럼 선형 탐색으로 작성할 경우 코드가 짧지만 효율적인 측면에서는 좋지 않다. 만약 L의 길이가 어마어마하게 클 경우 이는 O(n)의 복잡도를 갖기 때문이다. 반면 이진 탐색의 경우 비록 코드가 길지만 시간 복잡도가 O(logn)이기 때문에 훨씬 효율적이다.

 

 

이진 탐색을 구현하는 알고리즘에 대한 더 자세한 설명은 아래를 참고하면 된다.

https://yoonhwis.tistory.com/163

 

 

---

 

선형 탐색과 이진 탐색 차이점 비교

 

	선형 탐색	이진 탐색
검색 방법	배열의 처음부터 끝까지 순차적으로 탐색	정렬된 배열을 절반씩 범위를 줄여가며 탐색
배열 정렬 요구	상관없음	반드시 정렬되어 있어야 함
평균 시간 복잡도	O(n)	O(log n)
공간 복잡도	상수 공간을 사용하므로 O(1)	상수 공간을 사용하므로 O(1)
데이터 크기와 성능	작은 배열 또는 리스트에 적합 데이터 크기에 대한 제한 없음	대량의 데이터에 대해 효과적 큰 배열에서 빠른 검색 제공

 

 

---

 

모든 자료 구조와 알고리즘에 대해 알아보고 싶다면?

https://yoonhwis.tistory.com/135

자료구조와 알고리즘