이진 탐색

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
이는 시간복잡도 O(logN)을 보장한다.

이진 탐색 알고리즘은 재귀 함수와 반복문을 통해 구현할 수 있다.
반복문을 이용한 binary search

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

def main():
    n, target = map(int, input().split())
    array = list(map(int, input().split()))

    result = binary_search(array, target, 0, n-1)
    if result is None:
        print('원소가 존재하지 않습니다.')
    else:
        print(result + 1)
        
main()

재귀함수를 이용한 binary search

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)

def main():
    # n(원소의 개수)과 target(찾고자 하는 값) 입력 받기
    n, target = map(int, input().split())
    # 전체 원소 입력 받기
    array = list(map(int, input().split()))

    # 이진 탐색 수행 결과 출력
    result = binary_search(array, target, 0, n - 1)
    if result is None:  # result == None 으로 하면 노란줄 뜸 ㅋㅋ
        print("원소가 존재하지 않습니다.")
    else:
        print(result + 1)  # 인덱스 값을 출력하는 거니까 1 더해줘야함

main()

참고로 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다.
이 때, 입력 데이터가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다.
이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간초과를 피할 수 있다.

import sys

input_data = sys.stdin.readline().rstrip()
# rstrip() -> 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거해줌.

print(input_data)
# Hello, Coding Test!(Enter)
-> Hello, Coding Test!

참고

해당 블로그는 나동빈님의 '이것이 취업을 위한 코딩 테스트다. with 파이썬' 교재와 유튜브 강의를 참고하여 작성되었습니다.