이진 탐색 (Binary Search)

1. 이미 정렬된 데이터
2. 시작, 끝점, 중간점 필요
3. <찾으려는 데이터 & 중간점>을 반복적으로 비교
4. 재귀 or 반복문

• 재귀를 이용한 이진 탐색

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)

• 반복문을 이용한 이진탐색

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://programmers.co.kr/learn/courses/30/lessons/72412
https://programmers.co.kr/learn/courses/30/lessons/64062
https://programmers.co.kr/learn/courses/30/lessons/43238