이진 탐색 알고리즘

 

이진 탐색

: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

시간 복잡도 : O(log N)

 

# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end) :
    if start > endd :
    	return None
    # 찾은 경우 중간점 인덱스 반환
    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(찾고자 하는 값)을 입력 받기
 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)

 

 

# 이진 탐색 소스코드 구현 (반복문)
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

 

 

 

이진 탐색 라이브러리

bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

 

 

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

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))

#값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, 1, 3))

 

 

 

 

파라메트릭 서치 -> 이진탐색으로 해결!

: 최적화 문제를 결정 문제 (예 혹은 아니오)로 바꾸어 해결하는 기법

(특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제)

 

 

 

큰 탐색 범위(ex. 0~10억) -> 이진탐색!!!

 

'현재 이 높이로 자르면 조건을 만족할 수 있는가?' 확인 -> '예' or '아니오' -> 탐색 범위 좁혀서 해결

 

중간점의 값은 시간이 지날수록 '최적화된 값'이 됨

 

# 떡의 개수(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
        # 떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
        if total < m :
        	end = mid - 1
        # 떡의 양이 충분한 경우 더 자르기 (오른쪽 부분 탐색)
        else :
        	result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기ㅔ서 resultㅔ 기록
            start = mid + 1

 

 

 

 

시간 복잡도 O(log N)

데이터가 정렬되어 있기 때문에 이진탐색 수행!

특정 갑시 등장하는 첫번쨰 위치와 마지막 위치를 찾아 위치 차이를 계산

 

from bisect import bisect_left, bisect_right

#값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
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()) #데이터의 개수 N, 찾고자 하는 값 x 입력받기
 array = list(map(int, input().split()))) # 전체 데이터 입력받기
 
 # 값이 [x, x] 범위에 있는 데이터의 개수 계산
 count = count_by_range(array, x, x)
 
 #값이 x인 원소가 존재하지 않는다면
 if count == 0 :
 	print(-1)
 #값이 x인 원소가 존재한다면
 else :
 	print(count)

 

 

 

 

 

 

 

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5