[Algorithm] 이분탐색

이분 탐색 알고리즘

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

단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 $log_2 N$에 비례합니다. 

다시 말해, 이진 탐색은 탐색범위를 절반씩 줄이며, 시간 복잡도는  $O(log_2 N)$ 을 보장합니다. 

 

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

def binary_search(arr , target , start , end) : 
	if start > end : 
    	return None
    mid = (start + end) // 2 
    
    if arr[mid] == target : #만일 찾았을 경우 인덱스 반환 
    	return mid
    
    elif arr[mid] > target : #만일 중간점 값보다 찾고자 하는 값이 작은 경우 
    	return binary_search(array , target , start , mid-1) #끝 점을 중간점 -1로 지정 
    else : #만일 중간점 값보다 찾고자 하는 값이 클 경우 
    	return binary_search(array , target , mid-1 , end) #끝 점을 중간점 +1로 지정  
        
n , target = 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(arr , target , start , end) : 
	while start <= end :
    	mid = (start + end) // 2 
    	if arr[mid] == target : #만일 찾았을 경우 인덱스 반환 
    		return mid
    
    	elif arr[mid] > target : #만일 중간점 값보다 찾고자 하는 값이 작은 경우 
    		end = mid -1  
    	else : #만일 중간점 값보다 찾고자 하는 값이 클 경우 
    		start = mid +1 
	return None 
        
n , target = 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)

 

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

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

from bisect import bisect_left , bisect_right 

a = [1,2,3,4,4,8] 
x = 4 

print(bisect_left(a,x)) 
print(bisect_right(a,x)) 


#실행결과 
2
4

 

 

 

 

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

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)) 
 
 #실행결과 
 2 
 6

 

4. 파라메트릭 서치(Parametric Search) 

• 파라메트릭 서치란,  최적화 문제를 결정문제('예' 혹은 '아니요') 로 바꾸어 해결하는 기법이다. 
  • 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

 

5. 이진 탐색 기초 문제 풀이 

문제1. 떡볶이 떡 만들기 

 

Q. 절단기에 높이 (H)를 지정하면 줄지어진 떡을 한번에 절단한다. 높이가 H보다 긴 떡은 H의 윗부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19,14,10,17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15,14,10,15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4,0,0,2cm 이다. 손님은 6cm 만큼의 길이를 가져간다. 

 

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에서 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요. 

 

• 적절한 높이를 찾을 때 까지 이진 탐색을 수행하여 높이 H를 반복해서 조정한다. 
• '현재 이 높이로 자르면 조건을 만족하는가?' 의 여부에 따라 탐색범위를 좁혀나간다. 
• 중간점의 값은 시간이 지날수록 '최적화된 값' 이기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때 마다 중간점의 값을 기록하면 된다. 

#떡의 개수와 요청한 떡의 길이를 입력 
n ,m - list(map(int,input().split()) 

#각 떡의 개별 높이 정보를 입력 
arr = list(map(int,input().split()) 

#시작과 끝점 설정 
start = 0 
end = max(arr) 

#이진탐색 수행 
result = 0 
while start <= end :
	total = 0
    mid = (start+end) // 2 
    
    for x in arr :
    	if x > mid : 
        	total += x-mie 
    #떡의 양이 부족한 경우 떡의 높이를 낮추기 
    if total < m :
    	end = mid -1 
    #떡의 양이 충분한 경우 떡의 높이를 높이기 
   else :
   	result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 저장 
    start = mid + 1
    
print(result)

 

 

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

 

Q. N개의 원소를 포함하고 있는 수열일 오름차순으로 정렬되어 있을 때, 수열에서 x 가 등장하는 횟수를 계산하세요. 

 

앞에서 언급했던 ,특정 범위안에 있는 데이터 개수 구하기를 활용하면 될 것이라고 생각된다. 

from bisect import bisect_left , bisect_right 

N ,x = map(int,input().split()) 
num_list = list(map(int,input().split())) 

if x not in num_list :
	print(-1) 
    
right_index = bisect_left(num_list , x) 
left_index = bisect_left(num_list ,x) 

print(left_index - right_index)

 

 

🌰참고자료 

https://www.youtube.com/watch?v=94RC-DsGMLo

https://www.youtube.com/watch?v=1vZijMmhGNw