[알고리즘] 이진 탐색 정리

이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색

• 시작, 끝, 중간점이 있음
  • 중간점은 소수점 이하 제거한 값 ( 중간이 명확히 안나눠지는경우 )
• 리스트가 정렬이 되어 있어야만하다
• O(logN)
• 순차 탐색은 데이터를 앞에서부터 탐색함 ( 이진과는 다름 )

#재귀
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)

#반복문
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()))

res = binary_search(array,target,0,n-1)

if res == None: print("원소 존재하지 않음")
else: print(res + 1) #인덱스 값이므로 res + 1을 해줘야 한다

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

파라메트릭 서치

• 이진 탐색 사용
• 최적화 문제 → 결정문제 형태를 바꾸어 해결 ( 결정문제는 예 or 아니오 로 바꿔 해결하는 방법 )
  • 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 탐색 범위가 너무 크면 이진탐색을 생각해야 한다.

문제1) 떡볶이 떡 만들기

수행과정

• 떡볶이의 길이는 절단기로 일정하게 맞춰짐
• 절단기 높이 (H) 일때, 떡의 길이가 h이상이면 잘리고, 이하면 안잘림
  • ex) 19, 14, 10, 17 일때, h =15이면 → 4,0,0,2로 손님은 6cm를 가져감
• M길이 요청시, 적어도 M만큼의 떡을 얻기위해 절단기에 설정할 수 있는 높이의 최대

idea

• 적절한 높이를 찾을떄까지, 이진 탐색
• 0~n 일때, n이 너무 커서 조건 범위가 크면, 이진 탐색 체크하기 ( n ≥ 10억이상 )

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

start = 0
end = max(array)  #가장 긴 떡 길이
res = 0

while (start <= end):
	total = 0
	mid = (start + end) // 2
	for x in array:  #x는 현재 떡의 길이
		if x > mid:  #잘랐을때 떡의 양 계산
			total += x - mid

	if total < m:  #떡의 양이 부족하면 더 자르기
		end = mid - 1
	else :  #떡의 양이 충분한 경우 덜 자르기 ( m이상, 떡갖기)
		res = mid # 최대한 덜 잘렸을떄가 정답
		start = mid + 1
print(res)

문제2) 정렬된 배열에서 특정 수의 개수 구하기

수행 과정

• N개 원소를 가진 수열일 오름차순, 이때 x가 등장하는 횟수?
• O(logN) 으로 조건이 정해져 있어서, 알고리즘을 설계하지 않으면 시간초과가 된다( 선형탐색은 안됨)

idea

• 이진탐색 사용
• 특정값이 존재하는 첫번째 위치와 끝 위치를 찾아서 횟수 계산하기

from bisect import bisect_left, bisect_right

n,x = map(int,input().split())
array = list(map(int,input().split()))

# 배열에서 특정 범위 원소 개수 구하기
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

countNum = count_by_range(array,x,x)
if countNum == 0:
	print(-1)
else;
	print(countNum)

이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색

• 시작, 끝, 중간점이 있음
  • 중간점은 소수점 이하 제거한 값 ( 중간이 명확히 안나눠지는경우 )
• 리스트가 정렬이 되어 있어야만하다
• O(logN)
• 순차 탐색은 데이터를 앞에서부터 탐색함 ( 이진과는 다름 )

#재귀
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)

#반복문
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()))

res = binary_search(array,target,0,n-1)

if res == None: print("원소 존재하지 않음")
else: print(res + 1) #인덱스 값이므로 res + 1을 해줘야 한다

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

파라메트릭 서치

• 이진 탐색 사용
• 최적화 문제 → 결정문제 형태를 바꾸어 해결 ( 결정문제는 예 or 아니오 로 바꿔 해결하는 방법 )
  • 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 탐색 범위가 너무 크면 이진탐색을 생각해야 한다.

문제1) 떡볶이 떡 만들기

수행과정

• 떡볶이의 길이는 절단기로 일정하게 맞춰짐
• 절단기 높이 (H) 일때, 떡의 길이가 h이상이면 잘리고, 이하면 안잘림
  • ex) 19, 14, 10, 17 일때, h =15이면 → 4,0,0,2로 손님은 6cm를 가져감
• M길이 요청시, 적어도 M만큼의 떡을 얻기위해 절단기에 설정할 수 있는 높이의 최대

idea

• 적절한 높이를 찾을떄까지, 이진 탐색
• 0~n 일때, n이 너무 커서 조건 범위가 크면, 이진 탐색 체크하기 ( n ≥ 10억이상 )

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

start = 0
end = max(array)  #가장 긴 떡 길이
res = 0

while (start <= end):
	total = 0
	mid = (start + end) // 2
	for x in array:  #x는 현재 떡의 길이
		if x > mid:  #잘랐을때 떡의 양 계산
			total += x - mid

	if total < m:  #떡의 양이 부족하면 더 자르기
		end = mid - 1
	else :  #떡의 양이 충분한 경우 덜 자르기 ( m이상, 떡갖기)
		res = mid # 최대한 덜 잘렸을떄가 정답
		start = mid + 1
print(res)

문제2) 정렬된 배열에서 특정 수의 개수 구하기

수행 과정

• N개 원소를 가진 수열일 오름차순, 이때 x가 등장하는 횟수?
• O(logN) 으로 조건이 정해져 있어서, 알고리즘을 설계하지 않으면 시간초과가 된다( 선형탐색은 안됨)

idea

• 이진탐색 사용
• 특정값이 존재하는 첫번째 위치와 끝 위치를 찾아서 횟수 계산하기

from bisect import bisect_left, bisect_right

n,x = map(int,input().split())
array = list(map(int,input().split()))

# 배열에서 특정 범위 원소 개수 구하기
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

countNum = count_by_range(array,x,x)
if countNum == 0:
	print(-1)
else;
	print(countNum)