1. 이진 탐색이란

• 순차 탐색: 리스트 안의 특정 데이터를 찾기 위하여 데이터를 하나씩 확인한다.
• 이진 탐색: 정렬된 리스트 내에서 탐색의 범위를 절반씩 줄여가며 원하는 데이터를 찾는 방법이다.
  • 시작점, 중간점, 끝점을 이용하여 탐색의 범위를 설정한다.
• 시간 복잡도: 단계마다 탐색의 범위를 2로 나누어 탐색하는 것과 동일하므로 $log_{2}N$에 비례한다. 따라서 시간 복잡도는 $O(logN)$을 보장한다.

2. 이진 탐색의 동작법

3. 이진 탐색 구현(with Python)

3.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 = list(map(int, input().split()))

array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1,"번째에 값이 있습니다.")

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

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

n, target = list(map(int, input().split()))

array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1,"번째에 값이 있습니다.")

그림 폰트 출처: 제주특별자치도, 제주서체, https://www.jeju.go.kr/jeju/symbol/font/infor.htm
참고 서적: 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈, 한빛미디어
참고 강의: 나동빈님 유튜브 강의