👀 Binary Search 👀

intro

🐧 순차 탐색 - 선형 탐색) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 (가장 기본적인 형태 - 한 개씩 확인)

🐧 이진 탐색) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색(시작점, 끝점, 중간점을 이용하여 탐색 범위 설정)

 

※ 이진 탐색은 순차 탐색에 비해 탐색 범위가 훨씬 줄어들기 때문에 시간 복잡도는 log시간을 보인다.

 

Q. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기

0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18

 

① 시작점) index 0, 중간점) index 4, 끝점) index 9
→ 중간점이 2개 존재한다면, 소수점은 제외한 앞부분을 설정한다

→ 4가 중간점 기준 왼쪽에 존재함을 확인하면, 중간점 기준 오른쪽 탐색 x

 

② 시작점) index 0, 중간점) index 1, 끝점) index 3

→ 중간점 기준 4가 오른쪽에 존재하므로, 중간점 기준 왼쪽 탐색 x

 

③ 시작점, 중간점) index 2, 끝점) index 3

→ 중간점에 위치한 원소가 우리가 찾고자 하는 원소임을 알 수 있다.

 

※ 단계마다 탐색 범위를 2로 나누기 때문에, 연산횟수는 $\log_2 N$에 비례

 

※ 따라서, 이진탐색의 시간복잡도는 $O(log N)$ ※

binary search python

Q. binary search하는 원소의 갯수와 찾고자 하는 값인 target을 입력받는다. 그리고, target이 존재한다면, '몇 번째에 존재'하는지 출력

 

① 재귀 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start+end)//2
    if array[mid] == target:
        return mid #중간점이 target이면 끝!
    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('no target found')
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
    return None

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('no target found')
else: print(result+1)

 

★ start index <= end index인 동안 계속 진행

특정 원소 빈도 수 구하기

(1) binary search를 활용한 left / right index 각각 구하기

🐧 먼저 주어진 배열을 정렬하고 난 뒤, 정렬된 배열에서 특정 원소가 몇 개 존재하는 지 알고 싶을 때 binary search algorithm을 적용할 수 있다. 특정 원소가 왼쪽 기준 첫 번째로 등장하는 index를 A라 하고, 오른쪽 기준 첫 번째로 등장하는 index + 1을 B라고 한다면 특정 원소의 빈도수는 B-A로 쉽게 구할 수 있다. 이 때 A와 B를 구하는 과정을 binary search 활용할 수 있다.

 

이 때, left는 말 그래도 왼쪽 기준 첫번째 등장 원소의 index이지만, right는 오른쪽 기준 첫번째 등장 원소의 index + 1이다

오른쪽 주의

 

🐧 구하고자 하는 특정 수를 target이라 하고 이미 정렬된 array를 l이라 하자, A와 B를 각각 left()와 right()로 구하고자 한다면 아래와 같이 구할 수 있다.

def left(target, l):
    st,en=0,len(l)
    while st<en:
        mid=(st+en)//2
        if l[mid]>=target:
            en=mid
        elif l[mid]<target:
            st=mid+1
    #when st==en
    return st

def right(target, l):
    st,en=0,len(l)
    while st<en:
        mid=(st+en)//2
        if l[mid]>target:
            en=mid
        elif l[mid]<=target:
            st=mid+1
    #when st==en
    return st

 

★ left()

① st와 en 각각 index 0 / len(l)이라 한다. 이 때 , en index를 맨 끝의 원소 index + 1에 주의(그래야만 배열에 원소가 1개 있을 때도 적용가능)

 

② st < en인 동안 while문 돌림 (st와 en이 같을 때 while문 종료)

 

③

(1) l[mid] > target라면 en을 mid (왜냐면 target의 연속된 배열은 mid -1 까지의 앞에 존재하고 / 만약 target이 없다면 최대 mid 까지 존재)

(2) l[mid] < target라면 st를 mid+1 (왜냐면 target의 연속된 배열은 mid + 1부터 끝까지에 존재하고 / 만약 target이 없다면 최소 mid + 1부터 존재)

 

→ Q. en을 mid-1로 하지 않는 이유

ex) 예를 들어 아래 그림에서 22가 아닌, 23의 left를 찾는다고 하자. 그러면 23의 left는 mid인 en이 되므로, en은 mid로 항상 설정(위 오른쪽 index는 항상 마지막 등장 원소 + 1이기 때문)

 

(3) l[mid] == target이라면 left는 적어도 mid의 index보다 크지는 않겠다는 걸 알기 때문에, 우리는 left를 구하는 것이므로 탐색 범위를 end를 mid로 해서 mid 기준 mid 포함 왼쪽 범위로 절반으로 줄일 수 있다.

 

④ while문 종료될 때는 st와 en이 같을 때이므로 그 때 st값을 left값으로 return

 

★ right()

①② 모두 위 left()와 동일

 

③

(1) l[mid] > target이라면 en을 mid

(2) l[mid] < target이라면 st를 mid + 1

(3) l[mid] == target이라면 right는 적어도 mid + 1부터 존재. 즉 오른쪽 부분이므로 위 left와 이 부분만 다름

 

④ 위 left()와 동일

 

※ 아래 예시 그림 array에서 22를 target으로 찾는다고 가정하고 그림 시각화하며 코드 진행하면 이해하기 훨씬 쉽다

(2) 함수 사용 bisect_left() / bisect_right()

★ 위 직접 구현한 binary search 알고리즘을 매우 쉽게 bisect_left() / bisect_right() 함수를 구현해 바로 풀 수 있다.

 

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

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

from bisect import bisect_left, bisect_right
a = [1,2,4,4,8]
x = 4
print(bisect_left(a, x)) #2
print(bisect_right(a, x)) #4

 

→ 즉, x가 배열 a에서 삽입될 수 있는 가장 최솟값의 index와 최댓값의 index가 bisect_left와 bisect_right 결과 나오게 된다.

→ bisect_left 결괏값: x가 들어갈 수 있는 범위의 맨 왼쪽 원소 index

→ bisect_right 결괏값: x가 들어갈 수 있는 범위의 맨 오른쪽 원소 '그 다음 원소' index

 

🐧 응용해서, 아래와 같이 '값이 특정 범위에 속하는 데이터의 개수'를 구할 수도 있다.

★ 값이 A와 B 사이(둘 다 포함)에 있는 데이터의 개수를 구하고 싶다면 bisect_left()에 A / bisect_right()에 B를 넣어 B-A가 개수

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]

#값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4)) #2

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

* Binary Search 대표 유형 문제풀이>

Q1. 떡볶이 떡 만들기

Q. 오늘 라이언은 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 라이언네 떡볶이 떢은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다. 손님이 왔을 때 요청한 총 길이가 M일 때 '적어도 M'만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 '최댓값'을 구하는 프로그램을 작성하세요.

 

 

① 절단기의 높이가 0이상 10억이하인 매우 큰 범위에 들어가기 때문에 단순 선형 탐색이 아닌, 이진 탐색을 수행해야 한다

② 여러 경우의 수로 나누어서 잘린 떡의 길이 합이 M보다 큰 지, 아닌 지 두 가지 결과 가짓수에 의해 탐색 범위를 늘리거나 줄일 수 있으므로 이진탐색 유형임을 알 수 있다.

 

▶ 즉, 시간이 지날수록 중간점의 값이 '최적화된 값'으로 변하므로, 이진탐색을 수행하면서 중간점의 값을 계속 update하면 된다

n,m=list(map(int,input().split(' ')))
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:
        #잘랐을 때 떡의 양
        if x > mid:
            total+=x-mid
    #떡의 양이 부족하면 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end=mid -1
    #떡의 양이 충분하면 덜 자르기 (오른쪽 부분 탐색)
    else:
        res=mid
        start=mid+1
#최종적인 res가 구하고자 하는 답
print(res)

Q2. 정렬된 배열에서 특정 수의 개수 구하기

Q. N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

※ 단, 이 문제는 시간복잡도 $O(logN)$으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.

 

▶ 두 index의 차이로, 원하는 value의 범위 또는, 그 value값 자체의 개수를 구할 수 있다.

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)

---

이코테 2021

BaaarkingDog