[알고리즘][검색] 이진 탐색(Binary Search) - Python

1. 이진 탐색(Binary Search) 이란? 

- [나무위키] 이진 탐색(Binary Search)는 오름차순으로 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색합니다.

- 대학생때 많이들 하는 '업다운' 게임과 같은 방식입니다!

 

<그림으로 이해하는 이진탐색>

https://gaandlaneeraja.medium.com/binary-search-explanation-related-problems-java-8d87b10892e4

 

2. 이진 탐색의 파이썬 코드

2.1 재귀함수로 구현한 이진 탐색

def binary_search(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid+1, end)
    

# n(원소의 개수), target(찾고자 하는 문자열)

result = binary_search(array, target, 0, n-1)
print(result+1)

 

2.1 반복문으로 구현한 이진 탐색

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid-1
        
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 오른쪽 확인
        else:
            start = mid+1
    return None

        
result = binary_search(array, target, 0, n-1)

- 그림 설명이 필요없이 너무나 심플해서 따로 설명 이미지를 첨부하지 않았습니다!

 

3. 이진 탐색의 시간 복잡도 

 - 이진탐색은 한번 확인할 때마다 원소가 절반씩 줄어든다는 점에서 시간복잡도가 O(longN)입니다.

 

 

 

<참고> '이것이 코딩 테스트다 with 파이썬'

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고