이진 검색(Binary search)과 선형 검색(Linear search) 비교하기

이진 검색 및 선형 검색은 요소 목록에서 특정 요소를 검색하는 데 사용되는 두 가지 알고리즘이다. 둘 다 동일한 목적을 수행하지만 서로 다른 상황에 더 적합하게 만드는 몇 가지 주요 차이점이 있다.

이진 검색 (Binary search)

이진 검색은 정렬된 요소 목록에서 특정 요소를 검색하는 데 사용되는 알고리즘이다. 원하는 요소를 찾을 때까지 반복적으로 목록을 반으로 나누는 방식으로 작동한다.

다음은 코드에서 이진 검색을 구현하는 방법의 예다.

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

이 예에서 함수는 정렬된 목록(arr)과 찾고자 하는 요소(x)를 입력으로 사용한다. 그런 다음 루프를 사용하여 요소를 찾거나 요소가 목록에 없다는 것이 명확해질 때까지 반복적으로 목록을 반으로 나눈다.

이진 검색의 시간 복잡도는 O(log n)이며, 이는 검색을 수행하는 데 걸리는 시간이 목록의 크기에 따라 대수적으로 증가함을 의미합니다. 이렇게 하면 큰 목록에 대한 선형 검색(아래에서 설명)보다 훨씬 빠릅니다.

 

선형 검색 (Linear search)

선형 검색(순차 검색이라고도 함)은 요소 목록에서 특정 요소를 검색하는 데 사용되는 알고리즘이다. 원하는 요소를 찾을 때까지 목록의 각 요소를 하나씩 확인하는 방식으로 작동한다.

다음은 코드에서 선형 검색을 구현하는 방법의 예다.

def sequential_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

이 예에서 함수는 목록(arr)과 찾고자 하는 요소(x)를 입력으로 사용한다. 그런 다음 루프를 사용하여 원하는 요소를 찾을 때까지 목록의 각 요소를 확인한다.

선형 검색의 시간 복잡도는 O(n)이며, 이는 검색을 수행하는 데 걸리는 시간이 목록의 크기에 따라 선형적으로 증가함을 의미한다. 이렇게 하면 큰 목록에 대한 이진 검색보다 속도가 느리지만 목록을 정렬할 필요는 없다.

 

그렇다면 어떤 알고리즘을 사용해야 할까?

실제로 애플리케이션의 특정 요구 사항에 따라 다르다. 크고 정렬된 목록이 있고 특정 요소를 검색해야 하는 경우 이진 검색이 적합하다. 큰 목록을 순차적으로 검색하는 것보다 훨씬 빠르고 짧은 시간 내에 요소를 찾을 수 있기 때문이다. 반면 목록이 작거나 목록이 정렬되지 않은 경우 선형 검색이 적합할 것이다.