[알고리즘] 선형 탐색과 이진 탐색

선형 탐색 (Linear Search)

순차 검색이라고도 부르며 데이터가 모인 집합의 처음부터 끝까지 하나하나 비교하며 원하는 값을 찾아내는 알고리즘.

데이터 배열이 정렬되어 있지 않아도 가능하고, 난이도가 쉽지만, 데이터의 양이 많아질수록 소요되는 시간이 많아진다.

브루트-포스처럼 모든 케이스를 결국 보는 것과 같다고 생각..?

시간 복잡도는 데이터의 길이 n의 O(n) 이다.

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

 

 

이진 탐색 (Binary Search)

이분 탐색이라고도 부르며, 반으로 나누어 연산하기 때문에 다음과 같은 이름이 붙었다.

이진 검색은 중간값부터 탐색을 시작하기에 중간값을 찾기 위해 데이터 배열이 정렬되어 있는 전제가 필수이다.

찾으려는 값인 key가 있다면 

1. 배열의 중간 값을 가져온다

2. 중간 값과 key를 비교한다

 2-1. 중간 값이 key와 같다면 종료한다

 2-2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 다시 1번 과정부터 진행한다.

 2-3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 다시 1번 과정부터 진행한다. 

3. 더 이상 탐색할 구간이 없다면 종료한다. (탐색 실패)

시간 복잡도는 O(log n)이다.

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        # Check if x is present at mid
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

 

 

두 gif로만 비교해도 정렬된 기준, 이진 탐색의 속도가 훨씬 빠르고 효율적인 것을 볼 수 있다.