이진탐색 (Binary search)

탐색 범위를 두 부분으로 분할하면서 찾는 방식

• 반복할 때마다 검색 범위가 반으로 줄어듬
  -> 검색속도 빠름

• 시간복잡도
  전체 탐색 : O(N)
  이분 탐색 : O(logN)

• 자료가 정렬된 상태여야 함

검색과정

1. 자료 중앙에 있는 원소 고름
2. 중앙 원소와 찾고자 하는 목표 비교
3. 중앙 원소가 목표보다 크면 중앙 기준으로 왼쪽을 검색범위로
   목표보다 작으면 중앙 기준 오른쪽을 검색범위로
4. 다시 1번 부터 키 값 찾을 때까지 반복

• Ex. 7을 찾는 경우

'''
7
7
2 4 7 9 11 19 23
'''

def binary_search():
    start = 0
    end = N-1
    while start <= end :

        center = (start + end) // 2 
        print(center)
        if key > arr[center] : 
            print('왼')
            start = center + 1
            
        elif key < arr[center] : 
            print('오')
            end = center - 1
            
        else:
            return f'{center}에 있음'
        
    return f'없음'
        
            
N = int(input()) # 배열의 크기 
key = int(input()) # 찾고자 하는 값
arr = list(map(int,input().split())) # 배열 
print(binary_search())