[Algorithm] 탐색(선형탐색, 이진탐색)이란? / Python

    반응형
    SMALL

    탐색이란?

    예를 들어 도서관에서 특정 책을 찾는 과정을 탐색이라고 할 수 있다. 즉, 필요한 정보를 찾는 과정을 탐색이라고 하고, 필요한 정보를 찾는 다양한 방법을 탐색이라고 생각하면 된다.

     

    탐색의 종류로는 대표적 선형 탐색 알고리즘(Linear Search algorithm)이진 탐색 알고리즘(Binary Search Algorithm)이 존재한다.

     

    선형 탐색 알고리즘(Liner Search Algorithm)?

    우선 컴퓨터가 어떤 식으로 탐색을 하는 가 생각해보면, 가장 기초적인 방법은 처음 부터 끝까지 일일이 하나씩 찾으면서 탐색하는 방법이 있다. 이러한 방법을 선형 탐색 알고리즘이라고 한다. 선형 탐색 알고리즘은 왼쪽부터 하나씩 확인하는 방법이라고 생각하면 이해하기 쉽다.

    파이썬으로 선형 탐색을 구현해보면 아래와 같이 된다.

    def linear_search(element, some_list):
        for i in range(0, len(some_list)):
            if some_list[i] == element:
                return i
        return None

    위 코드를 보면 찾고자하는 값인 element를 넣고 검색하고자 하는 리스트를 some_list에 넣어서 for문을 통해 하나 씩 찾는 방법이다.

     

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

    이진 탐색 알고리즘은 이미 정렬이 되어있다고 가정하고 중간지점을 기준으로 반씩 제외하면서 찾는 방식이다. 예를 들어, [1, 2, 3, 4, 7, 9, 13]에서 2를 찾을 때 이진 탐색 알고리즘을 쓴다면 우선 중간지점은 4에서 비교해서 4보다 크다면 오른쪽에 찾는 값이 있을 것이고, 작다면 왼쪽에 찾는 값이 있다고 생각할 수 있다. 즉, 가운데 값과 목푯 값을 비요해서 절반 씩 줄이는 방법이라고 할 수 있다.

    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 some_list[mid_index] == element:
                return mid_index
            elif some_list[mid_index] >= element:
                end_index = mid_index - 1
            elif some_list[mid_index] <= element:
                start_index = mid_index + 1
        return None
    반응형
    LIST

    'Algorithm' 카테고리의 다른 글

    [Algorithm] 팰린드롬(palindrome)이란? / Python  (0) 2022.01.19

    댓글