선형탐색알고리즘(linear search algorithm) 과 이진탐색알고리즘(binary search algorithm)

프로그램에서 가장 간단하고 대표적인 알고리즘이 탐색 알고리즘이다. 기초적인 탐색 알고리즘에는 2가지가 있다. 선형탐색알고리즘이란, 순차적으로 원하는 결괏값을 탐색하는 것이다. 이진탐색알고리즘은 중간지점을 기준으로 반씩 제외하여 원하는 결괏값을 찾는 알고리즘이다. 각각의 알고리즘에 대해 조금 더 알아보고 코드로 적어보도록 하자.

 

 

 

 

 

 

 

1명을 찾기 위해 100만 명을 검사한다고 생각해 보자. 어떻게 찾는 것이 효율적일까? 선형탐색의 경우에 순차적으로 원하는 것을 찾는 방식이다. 만약 원하는 사람이 마지막에 있는 경우, 최악의 효율로 100만 번을 검사를 해야 원하는 사람을 찾을 수 있다. 이진탐색의 경우에는 최악의 경우는 20번이다. 생각보다 효율차이가 큰 것을 확인할 수 있다. 각각의 알고리즘에 대해 알아보자.

 

---

 

선형 탐색 알고리즘(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

 

linear_search 함수를 보면, element라는 찾고자하는 값과 some_list라는 조회할 배열을 인자로 받는다. 그래서 For문을 돌리면서 찾고자 하는 값이 나오면, 그 값을 리턴한다. 찾고자 하는 값이 없으면 None을 리턴한다. 사실 간단한 For 문으로 하나씩 조회하는 로직이 선형 탐색 알고리즘이라고 할 수 있다.

 

 

---

 

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

중간 지점을 기준으로 반씩 제외하여 확인하는 방식이다.

 

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1

    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

 

binary_search 함수를 보면, element라는 찾고자하는 값과 some_list라는 조회할 배열을 인자로 받는다. 그리고 이진 탐색 알고리즘은 pointer라는 개념이 등장한다. start_index가 검색하는 범위의 시작 지점이고, end_index가 검색 범위의 끝 지점이다. start_index와 end_index의 범위를 줄이면서 원하고자 하는 값을 찾는 것이 바로 이진 탐색 알고리즘이라고 할 수 있다. while 로직을 보면, 구하려는 값과 중간 값을 비교하여 포함되지 않는 쪽을 제외하고 다시 start_index와 end_index를 재설정하여 탐색 범위를 줄인다.

 

 

 

---

 

탐색 알고리즘 비교

선형 탐색과 이진 탐색의 결과물은 같다. 만약에 길이가 16인 list를 찾는다고 해보자. 선형 탐색 알고리즘 (linear search algorithm)에서는 가장 금방 되는 경우 1번 (처음 검사해서 찾음)이고, 가장 오래 걸리는 경우 16번이다. 이진 탐색 알고리즘(binary search algorithm)에서는 가장 금방 되는 경우 1번 (처음 검사해서 찾음) 가장 오래 걸리는 경우 4번 (리스트에 0이 없을 때 0일 찾는 경우 : (인덱스 기준이고 0은 작은 값이므로 외쪽으로 계속 찾게 됨) 16-8-4-2-1이면 첫 번째 자리와 비교했는데도 0이 아니므로 탐색 종료.)이다.

 

리스트 길이	선형 탐색	이진 탐색
16	최악의 경우 16번 탐색 필요	최악의 경우 4번 탐색 필요
32	최악의 경우 32번 탐색 필요	최악의 경우 5번 탐색 필요
64	최악의 경우 64번 탐색 필요	최악의 경우 6번 탐색 필요
128	최악의 경우 128번 탐색 필요	최악의 경우 7번 탐색 필요

 

선형 탐색은 리스트의 길이가 길어져지면 탐색 기간도 길어진다. 위의 표를 보면 선형 탐색을 쓰면 안 될 것 같다. 너무 비효율적으로 보인다. 하지만, 이진 탐색을 사용하려면 리스트가 정렬이 되어 있는 경우에만 사용가능하다. 즉, 정렬이 되어 있지 않는 리스트는 이진 탐색을 사용할 수 없고 선형 탐색을 사용하거나, 정렬 후에 이진 탐색을 사용해야 한다.

 

 

정리

선형탐색알고리즘(linear search algorithm)은 도서관에서 ㄱ부터 시작하는 도서를 하나씩 확인하면서 내가 찾는 책까지 찾는 방법이다. 이진탐색알고리즘(binary search algorithm)은 가운데 값과 목표 값을 비교하면서 탐색범위를 절반씩 줄이는 방법이다. 이진탐색알고리즘은 정렬을 한 후에 적용할 수 있다. 따라서 이진탐색 알고리즘 사용 전에 정렬 알고리즘도 동시에 적용이 필요하기 때문에, 복잡도를 따져본 후에 선형탐색 / 이진탐색 중에 더 적절한 것을 골라 사용하면 된다.