이진 탐색

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

• 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음

• 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다.

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반본적으로 비교해서 원하는 데이터를 찾는 것

방법 1. 재귀 함수 이용

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)

방법 2. 반복문 이용

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)

💡 꿀팁! Python으로 빠르게 입력값 받기

import sys
input = sys.stdin.readline.rstrip()

s = input()