7. 이진 탐색

✅ 이진 탐색 자료구조

✓ 이진 탐색 트리

• '왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드'을 성립한다
• 부모 노드부터 탐색한다
  

(+) 빠르게 입력받기

• 이진 탐색은 입력 데이터가 많거나 탐색 범위가 매우 넓다 -> input()대신 readline()함수를 사용하여 시간 초과를 예방하자

import sys
# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip()  #rstrip()함수를 호출해야 공백 기호 제거가능

✅ 이진 탐색 구현

• 정렬된 데이터에 한해 사용할 수 있다.
• 시간복잡도: O(log N)

✓ 이진 탐색 소스코드: 재귀적 구현

def binary_search(array, target, start, end);
	# 탐색할 데이터가 없는 경우
    if start > end:    
    	return None
    mid = (start+end)//2
    # target을 찾은 경우, 중간젖ㅁ 인덱스 반환
    if array[mid] == target:
    	return mid
    # 중간점의 값보다 target이 작은 경우: end를 mid-1로 변경(왼쪽 확인)
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 target이 큰 경우: start를 mid+1로 변경(오른쪽 확인)
    else:
    	return binary_search(array, target, mid+1, end)
        
# n(원소의 개수), target(찾고자 하는 값) 입력받기
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)  #인덱스 값에 1을 더함

✓ 이진 탐색 소스코드: 반복문 구현

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       

✓ 파이썬 이진 탐색 라이브러리

• bisect
  
• 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index  #두 값의 차는 해당 범위 데이터의 개수
    
# 배열 선언
a = [ 1,2,3,3,3,3,4,4,8,9]
# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4,4)) #2
# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3)) #6

✅ 이진 탐색 문제 풀이

✓ 파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제('예' 또는 '아니오')로 바꾸어 해결하는 것
  예시: 특정한 조건을 만족하는 가장 알맞는 값을 빠르게 찾는 최적화 문제
• 일반적으로 파라메트릭 서치는 이진 탐색으로 해결한다

1. 떡볶이 떡 만들기

• 문제 해결 아이디어
  - 높이(H)가 높을수록 떡은 조금 잘린다. 높이가 낮을수록 떡이 많이 잘린다
  • 높이가 10억 이하의 양의 정수이다(탐색 범위 매우 큼) -> 순차 정렬은 시간초과 예상. 이진 탐색으로 풀이한다.
  • '현재 높이로 자르면 조건에 만족하는가?' 확인 후, 조건에 따라서 범위를 좁혀간다.
  • 중간점 값을 시간이 지날수록 '최적화된 값'이 된다. 필요한 떡의 크기보다 크거나 같을 때마다 중간점 값을 기록한다.

# 떡의 개수(N)과 요청한 떡의 길이(M) 입력
n, m = list(map(int, input().split('')))
# 각 떡의 개별 높이 정보 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점, 끝점 설정
start = 0
end = max(array)  #가장 긴 떡의 높이를 끝점으로 설정

# 이진 탐색 수행(반복적)
result = 0
while(start<=end):
    total = 0
    mid = (start+end)//2
    for x in array:
    	# 잘라진 떡의 길이 계산
        if x > mid:   # 떡의 길이가 중간점보다 긴 경우 계산
        	total += x - mid
     # total값이 m값보다 작은 경우 더 많이 자르기(왼쪽 부분 탐색)
    if total < m:
    	end = mid - 1
     # total값이 m값보다 큰 경우 더 조금 자르기(오른쪽 부분 탐색)
     else:
        result = mid #최대한 덜 잘랐을 때가 정답이므로 mid값을 result로 기록해두기
     	start = mid + 1
        
# 정답 출력
print(result)

2. 부품 찾기

• 문제 해결 아이디어
  - 특정 데이터가 존재하는지 확인하는 문제
  • 이진 탐색, 계수 정렬, 집합 자료형(set()) 세 가지 방법으로 해결 가능

(1) 이진 탐색으로 구현

(2) 계수 정렬로 구현

• 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤, 리스트의 인덱스에 직접 접근하여 특정 인덱스에 부품이 있는지 확인

# N(가게의 부품 개수) 입력 받기
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split():
	array[int(i)] = 1
# M(손님이 확인 요청한 부품 개수) 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호 공백으로 구분 입력
x = list(map(int, input(),split()))

# 확인 요청한 부품 번호를 하나씩 확인
for i in x:
	if array[i] == 1:
    	print('yes', end=' ')
    else:
    	print('no', end=' ')

(3) 집합 자료형 이용

• set()함수는 집합 자료형을 초기화할 때 사용한다. 데이터 포함 여부 확인 시 속도가 매우 빠르다는 걸 기억하기.

# N(가게의 부품 개수) 입력 받기
n = int(input())
# 가게에 있는 전체 부품 번호를 입력받아서 집합(set) 자료형에 기록
array = set(map(int, input().split()))

# M(손님이 확인 요청한 부품 개수) 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호 공백으로 구분 입력
x = list(map(int, input(),split()))

# 확인 요청한 부품 번호를 하나씩 확인
for i in x:
	# 해당 부품이 존재하는지 확인
    if i in array:
    	print('yes', end=' ')
    else:
    	print('no', end=' ')

✓ 특정 수의 개수 구하기

• 문제 해결 아이디어
  - 데이터가 정렬되어 있으므로 이진 탐색 사용
  • 특정 값이 등장하는 첫 번째 위치, 마지막 위치의 차를 구한다
  • bisect 라이브러리를 활용한다

from bisect import bisect_right, bisect_left

def count_by_range(array, left_value, right_value):
	right_index = bisect_right(array, right_value)
    left_index - bisect+left(array, left_value)
    return right_index - left_index

#필요한 데이터 입력받기
n,x = map(int, input().split()) #데이터 개수, 찾고자 하는 값 x
array = list(map(int, input().split())) #전체 데이터

#값이 [x,x]범위에 있는 데이터 개수 계산
count = count_by_range(array, x,x)

if count==0:
	print(-1)
else:
	print(count)