이진 탐색 알고리즘

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다.

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
-> 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

ex. 시작점, 중간점, 끝점을 기준으로 내가 찾고자하는 원소가 중간점보다 작을 경우 중간점~ 끝점 까지는 탐색을 하지 않아도 된다.

      ➡️ 끝 점을 중간점 왼쪽으로 옮기고 중간점을 다시 설정한다.
      ➡️ 위 과정을 반복한다.

 

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례한다.
즉 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장한다.

 

파이썬 코드

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)


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)

 

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

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

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

 

from bisect import bisect_left, bisect_right

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

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

#실행 결과 2,4

 

이를 이용하여 특정 범위에 속하는 데이터 개수를 구할 수 있다.

 

from bisect import bisect_left, bisect_right

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]
print(count_by_range(a,4,4))
print(count_by_range(a,-1,3))

# 2,6 출력

 

파라메트릭 서치

최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

 

문제) 떡볶이 떡 만들기

엘은 여행가신 부모님 대신해서 떡집 일을 하기로했다. 엘네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

ex. 19, 14, 10, 17 길이의 떡이 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15가 된다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 총 6cm만큼의 길이를 가져간다.

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

 

문제 해결 아이디어)

적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다.

'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다.

절단기의 높이는 0부터 10억까지의 정수 중 하나이다. 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올리자!

시작점은 0, 끝점은 19, 중간점은 9이다. (만족)
시작점 10, 끝점 19, 중간점 14로 설정 (만족)

시작점 15, 끝점 19, 중간점 17 (만족X)

시작점 15, 끝점 16, 중간점 15 (만족)

➡️ 중간점의 값은 시간이 지날수록 '최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크기가 같을 때마다 중간점의 값을 기록하면 된다.

 

 

#직접 작성한 코드
n,m=map(int,input().split())

array=list(map(int, input().split()))
array.sort()
num=array[-1]-1

for i in range(m):
    count=0
    for j in array:
        if j<=num:
            continue
        else:
            count+=j-num
    
    if count==m:
        break
    num-=1

print(num)

#답안
start=0
end=max(array)

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
        start=mid+1

print(result)

 

 

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

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있다. 이때 이 수열에서 x가 등장하는 횟수를 계산해라.

예를 들어 수열 {1, 1, 2, 2, 2, 2, 3} 이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.

(조건: O(logN)으로 설계해라)

 

➡️ 선형 탐색으로는 시간 초과 판정을 받는다. 하지만 데이터가 정렬되어있기 때문에 이진 탐색을 수행하자.

특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다.

 

from bisect import bisect_left, bisect_right
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())
array=list(map(int, input().split()))

count=count_by_range(array,x,x)

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

 

참고) 이것이 취업을 위한 코딩 테스트다 with 파이썬