알고리즘 - 선형 탐색과 이진 탐색

탐색

저장된 정보들 중에서 원하는 값을 찾는 것.
탐색은 두 가지 방법이 있다. 하나는 선형 탐색, 다른 하나는 이진 탐색이다.

1. 선형 탐색 알고리즘(Linear Search Algorithm)

앞에서부터 하나하나 확인해서 값을 찾는 방법

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:   # 반복문을 돌려 값을 하나하나 확인한다.
            return i
 
    return None

print(linear_search(2, [2, 3, 5, 7, 11]))
-> 0

2. 이진 탐색 알고리즘(Binary Search Algorithm)

전체 값의 중간값을 찾고, 찾는 값이 중간값보다 작은지 큰지 확인한 후 중간값보다 크면 작은값들을 소거한다. 이러한 방식을 반복해서 원하는 값을 찾는 방법

def binary_search(element, some_list):
    start_index = 0    # 시작 인덱스를 설정
    end_index = len(some_list) - 1   # 마지막 인덱스를 설정
    
    while start_index <= end_index:   # 시작 인덱스와 마지막 인덱스가 같아질 때까지 반복해서 범위를 좁힌다.
        mid_index = (start_index + end_index) // 2   # 중간 인덱스를 구한다.
        
        if element == some_list[mid_index]:   # 찾는 값과 중간값을 비교
            return mid_index

        elif element > some_list[mid_index]:
            start_index = mid_index + 1    # 찾는 값이 중간값보다 더 크면 시작 인덱스 범위를 좁힌다.

        else:
            end_index = mid_index - 1    # 찾는 값이 중간값보다 더 작으면 마지막 인덱스 범위를 좁힌다.
    
    return None
    

print(binary_search(2, [2, 3, 5, 7, 11]))
-> 0

3. 선형 탐색과 이진 탐색 비교

선형 탐색은 하나하나 값을 찾기 때문에 전체값의 크기가 작으면 금방 찾을 수 있다. 그러나 전체값의 크기가 엄청나게 커지면 그만큼 범위가 커지기 때문에 커지면 커질수록 오래걸린다.

이진탐색은 값의 범위를 줄여나가서 찾기 때문에 전체값의 크기가 커져도 굉장히 빠른 시간내에 찾을 수 있다.

위의 이미지를 보면 확실하게 비교할 수 있다. 선형탐색은 값이 커지면 커질수록 탐색하는 값이 많아지고, 이진탐색은 탐색하는 값이 늘긴하지만 선형탐색에 비해 훨씬 적게 탐색하는 것을 확인 할 수 있다.

그러나 이진탐색은 찾는 값이 큰지 작은지 비교를 해서 찾기 때문에 값이 정렬된 상태여야만 가능하다.

** 출처

• 코드잇 - 알고리즘의 정석