[Python] 알고리즘의 종류, 종류별 예제 _ 이진탐색 (5/7)

• 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진탐색 : 정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 데이터를 탐색하는 방법
• 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정

전제조건 : 정렬되어있는 데이터

#binary search(이진탐색)

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

#재귀함수
def binary_search(array, target, start, end):
    if start > end: #start가 end보다 크다면 값이 없음.
        return None
    mid = (start + end) // 2
    if target == array[mid]:
        return mid
    elif target > array[mid]:
        return binary_search(array, target, mid + 1, end)
    elif target < array[mid]:
        return binary_search(array, target, start - 1, mid)

#반복문
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if target == array[mid]:
            return mid
        elif target > array[mid]:
            start = mid + 1
        elif target < array[mid]:
            end = mid - 1
    return None

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 없습니다.")
else:
    print(result)

이진탐색 라이브러리

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4
print(bisect_left(a,x)) : 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
print(bisect_right(a,x)): 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환
-------------------------------------
#return
2
4

 

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

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
	left_idx = bisect(array, left_value)
	right_idx = bisect(array, right_value)
	return right_idx - left_idx

array = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(array, 4, 4))
print(count_by_range(array,-1,3))
------------------------------------------------
#return
2
6

파라메트릭 서치(Parametric Search)

떡볶이 떡 만들기

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

start = 0
end = max(array)

result = 0
while(start <= end):
	total = 0
	mid = (end - start) // 2
	for x in array:
		if x > mid:
			total += mid - x
	if total < m:
		end = mid - 1
	else:
		result = mid
		start = mid + 1

print(result)

인수별로 조건에 만족하는지를 이진탐색으로 찾아가는 방법.