[알고리즘] 이진탐색 Binary Search
🍁

[알고리즘] 이진탐색 Binary Search

Created
2022/07/10
Tags
Binary Search
Algorithm
 
2022-07-05 @이영훈
 
이진탐색 알고리즘을 기록으로 남깁니다.
나동빈님의 이진 탐색 유튜브 영상을 참고하였습니다.
 

이진 탐색 (Binary Search)

이진 탐색 알고리즘은 오름차순 또는 내림차순으로 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.
 
notion image
 
 

이진 탐색 동작 과정

[문제 조건] 정렬된 10개의 데이터 중에서 값이 찾는값(target) 4인 원소를 찾습니다.
notion image
 
[Step1] 시작점(start)을 0번, 끝점(end)을 9번, 중간점(middle)을 (0 + 9) // 2 = 4 로 초기화 합니다.
notion image
 
[Step2] target이 중간점의 값(arr[middle])보다 작기 때문에 끝점을 중간점보다 하나 작게 설정합니다
  • end = middle - 1
notion image
 
[Step3] 이번에는 중간점 값(arr[middle])이 target보다 작기 때문에 시작점을 중간점보다 하나 더 크게 설정합니다.
  • start = middle + 1
notion image
 
 

이진 탐색의 시간 복잡도

  • 단계마다 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도는 O(logN)입니다.
  • 정렬된 데이터가 많을 때 (1억개 이상) 순차 탐색보다는 이진 탐색으로 접근하는 것이 좋습니다.
 
notion image
 
 

파이썬 코드

 
반복문으로 구현
Python
def binary_search(arr: List[int], target: int):
    start = 0
    end = len(arr) - 1

    while start <= end:
        middle = (start + end) // 2

        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            end = middle - 1
        else:  # arr[middle] < target:
            start = middle + 1

    return -1
 
 
재귀적으로 구현
Python
def binary_search(arr: List[int], target: int, start: int, end: int):
    if start > end:
        return -1

    middle = (start + end) // 2

    if arr[middle] == target:
        return middle
    elif arr[middle] < target:
        return binary_search(arr, target, middle + 1, end)
    else:  # arr[middle] > target:
        return binary_search(arr, target, start, middle - 1)