→ rstrip() : 엔터로 입력한 개행 제거용

순차탐색

: 앞에서부터 데이터 차례대로 확인

이진탐색

: 범위를 반으로 쪼개가며 탐색학

• 이미 정렬된 데이터에 대해
• 찾으려는 데이터와 중간점에 위치한 데이터를 반복 비교

→ 주로 탐색의 범위가 큰 상황에서 탐색 가정

: 코테에서 범위 2000만 넘어가면 이진탐색으로 접근해보기

구현

재귀로 구현

def binary_search(array, start, end, target):
	if start < end:
		return None
	mid = (start + end) // 2
	
	if array[mid] == target:
		return mid
	elif array[mid] > target:
		return binary_search(array, start, middle-1, target)
	else:
		return binary_search(array, middle+1, end, target)

반복문으로 구현

def binary_search(array, start, end, target):
	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

빠르게 입력받기

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

이분탐색의 세 유형

이분탐색 문제는 크게 세 유형으로 나뉜다고 삽고수가 알려줬다.
1. 어느 배열에서 x인 원소가 있는지 탐색
2. 어느 배열에서 조건을 만족하는 최대 길이 탐색
3. 어느 배열에서 조건을 만족하는 최소길이 탐색