# 이진 탐색 알고리즘

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

이진탐색

4 찾기

0     2     4     6     8    10    12    14    16    18
시작점                  중간점                         끝점

시작점 : 0 
중간점 : 4  > 만약 중간점이 소수점으로 나오면 소수점 이하 제거한 값이 중간 점
끝점   : 9
[숫자는 인덱스를 의미함]

1. 찾고자 하는 값과 중간점을 비교
찾고자 하는 값 (4) < 중간 점 (8) 라면,
끝점(현재는 18에 위치)을 중간 점의 왼쪽(6으로 이동)으로 옮긴다

0       2     4     6     8    10    12    14    16    18
시작점  중간점        끝점

소스코드

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개의 원소 갯수와 찾고자 하는 값 입력 받고,
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)