이진 탐색(Binary Search)

오늘의 포스팅은 탐색(serach) 알고리즘에 속하는 이진탐색(Binary Search)입니다! 

지금까지 원하는 기준으로  값을 정리하는 정렬

특정 순위의 요소를 찾는 선택 알고리즘들을 알아봤는데요!

이번에는 특정 값을 찾는 탐색 알고리즘에 대해 알아보겠습니다!

 

# 탐색알고리즘이란?

주어진 데이터에서 원하는 값을 찾는 것을 말하는데요

탐색알고리즘에는 순차탐색, 이진탐색, 깊이우선탐색(DFS), 너비우선탐색(BFS) 등이 있습니다! 

 

# 동작과정 

정렬된 데이터에서만 동작하는데욥!

중앙값과 타겟(찾을 값)을 비교하며 절반씩 탐색 범위를 줄여가며 탐색을 진행합니다!

총 3가지 경우로 구분할 수 있는데욥

 

1) 중앙값 == 타겟

-> 탐색 종료

2) 중앙값 > 타겟 

-> 중앙값 왼쪽 데이터셋 탐색

3) 중앙값 < 타겟 

-> 중앙값 오른쪽 데이터셋 탐색

# Python 코드

중앙값과 타겟값의 조건별로 지정해주기 때문에 구현이 간단합니다!

타겟값을 찾을시, 타겟값의 인덱스를 반환하며

탐색할 타겟값이 없다면, -1을 반환하도록 하였습니다

def binary_search(A, key, low, high):

    # 기본 조건: 탐색 범위가 남아 있을 때만 진행

    if low <= high:

        # 중앙값 계산

        middle = (low + high) // 2

       

        if key == A[middle]: # 중앙값 == 타겟

            return middle  # 탐색 성공, 값의 인덱스 반환

       

        elif key < A[middle]: # 중앙값 > 타겟

            return binary_search(A, key, low, middle - 1)

       

        else:  # 중앙값 < 타겟

            return binary_search(A, key, middle + 1, high)

   

    # 탐색값이 없을시 -1반환

    return -1

 

# 성능분석 - 시간복잡도

이진탐색은 중간값을 기준으로 절반씩 줄여가며 값을 찾기 때문에 밑이 2인 O(logn)의 시간복잡도를 보입니다!

 

간단한 예시로 16개의 자료에서 값을 탐색한다면,

처음부터 값을 하나씩 찾는다면 최악의 경우에 16번의 연산으로 값을 찾을 수 있지만

이진탐색은 최악의 경우에도 log16인 4번만에 값을 찾을 수 있습니다!

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))