이진(이분) 탐색

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
n = len(arr)
def binarySearch(arr, n, target):
    left = 0 # 시작 인덱스
    right = n - 1 # 끝 인덱스
    while left <= right:
        mid = (left + right) // 2 # 중간 인덱스
        if arr[mid] == target: # 타겟 숫자를 찾으면 True
            return True
        elif arr[mid] > target: # 중간 값이 더 크면 오른쪽 인덱스 -1를 해준다
            right = mid - 1
        elif arr[mid] < target: # 중간 값이 더 작으면 왼쪽 인덱스 + 1를 해준다
            left = mid + 1
    return False # 못찾으면 False
print(binarySearch(arr, len(arr), 9)) #=> True