★Binary Search Intermediate I - 7 Solved★

 

👩🏼‍🔬 binary-search의 핵심은 탐색 범위를 줄여, 원하는 target을 찾는 시간 복잡도를 $O(logN)$으로 줄인다는 데 있다.

 

👩🏼‍🔬 binary-search 간략 요약

① 주어진 array, 찾고자 하는 target, 시작 start와 끝 end - 4개가 주어진다.

② start와 end의 중간점 mid를 구한다(짝수이면 소수점 절사)

③ mid가 가리키는 값이 target이면 끝! target보다 크다면 end를 mid-1로, target보다 작다면 start를 mid+1로 설정

---

★ 13777 Hunt The Rabbit ★

※ binary-search 유일 Bronze 문제이지만 Intermediate 포스팅에 넣음 ※

 

def binary_search(n,l,start,end):
    a=[]
    while start<=end:
        mid=(start+end)//2
        a.append(mid)
        if l[mid]==n:break
        elif l[mid]>n:end=mid-1
        else:start=mid+1
    return a
while 1:
    n=int(input())
    if n==0:break
    l=[i for i in range(0,51)]
    start,end=1,50
    print(*binary_search(n,l,start,end))

 

👩🏼‍🔬 이분탐색에서 주의해야 할 부분은 start와 end의 설정 & 범위 indexing 올바른지 확인

→ 1부터 50까지 고정 길이를 탐색하므로, 일부러 list에 0을 추가해 index와 value값이 같게 해 혼동을 피함.

 

👩🏼‍🔬 이분탐색하면서 middle envelope을 계속 open하므로 mid값을 계속 빈 list에 집어넣으면서 update된 list의 값들을 쭉 출력해주면 됨

---

★ 1920 수 찾기 ★

 

import sys
input=sys.stdin.readline
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 -1
N=int(input())
A=sorted(list(map(int,input().split())))
M=int(input())
for x in map(int,input().split()):
    if binary_search(A,x,0,N-1)>=0:print(1)
    else:print(0)

 

👩🏼‍🔬 원하는 숫자가 있는지 이분탐색으로 찾는 문제, start와 end 주의해서 넣기, index start 0, 그리고 맨 끝 index N-1로 end 설정

---

★ 10815 숫자 카드 ★

 

import sys
input=sys.stdin.readline
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 -1
N=int(input())
arr=sorted(set(map(int,input().split())))
M=int(input())
for num in map(int,input().split()):
    if binary_search(arr,num,0,N-1)>=0:print(1,end=' ')
    else:print(0,end=' ')

 

👩🏼‍🔬 이분탐색의 정석! 중요한건, 탐색할 범위는 미리 sorted()로 정렬을 해줘야 하고, start와 end 잘 설정할 것!

---

★ 10816 숫자 카드 2 ★

 

from bisect import bisect_left, bisect_right
import sys
input=sys.stdin.readline
ans=[]
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

N=int(input())
l=list(map(int,input().split()))
l.sort()
M=int(input())
X=list(map(int,input().split()))

for x in X:ans.append(count_by_range(l,x,x))
print(*ans)

 

👩🏼‍🔬 이분탐색 이론 포스팅에서 소개한 대로, bisect_left와 bisect_right를 사용해 원하는 수의 개수를 구할 수 있다.

 

👩🏼‍🔬 또는 Counter(from collections) 함수 사용 가능: 빈도수가 들어간 hash-map

from collections import Counter
import sys
input=sys.stdin.readline

input()
l=input().split()
input()
X=input().split()

C = Counter(l)

print(*[C[key] for key in X])

 

👩🏼‍🔬 bisect_left / bisect_right 사용 없이 풀이

import sys
input=sys.stdin.readline

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


N=int(input())
cards=list(map(int,input().split()))
cards.sort()
M=int(input())
targets=list(map(int,input().split()))
for target in targets:
    x,y = left(target, cards), right(target, cards)
    print(y-x,end=' ')

 

👩🏼‍🔬 이분 탐색은 아니지만 hash map으로도 풀린다 (defaultdict() 사용)

import sys
input=sys.stdin.readline
from collections import defaultdict

freq=defaultdict(int)
N=int(input())
cards=list(map(int,input().split()))
for card in cards:
    freq[card]+=1
M=int(input())
l=list(map(int,input().split()))
for x in l:
    print(freq[x],end=' ')

---

★ 13706 제곱근 ★

 

N=int(input())
if N in [0,1]:
    print('01'[N])
else:
    start=2
    end=N//2
    while start<=end:
        mid=(start+end)//2
        if mid*mid == N:
            print(mid)
            break
        elif mid*mid > N:
            end=(mid-1)
        else: #mid*mid<N
            start=(mid+1)

 

👩🏼‍🔬 0과 1 제외 나머지 모든 제곱수의 제곱근은 N/2 이하의 값에 존재하므로 start = 2 / end = N/2에서 시작해 제곱수가 존재하면 바로 출력하는 전형적인 이분탐색 방식

---

★ 2776 암기왕 ★

 

import sys
input=sys.stdin.readline

def binary_search(target, l):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if target==l[mid]: return True
        elif target>l[mid]: start=mid+1
        else: end=mid-1
    return False
for _ in range(int(input())):
    N=int(input())
    ans=sorted(list(map(int,input().split())))
    M=int(input())
    Ml=list(map(int,input().split()))
    for x in Ml:
        print(int(binary_search(x,ans)))

 

👩🏼‍🔬 수첩2를 돌리면서 수첩1에 있는 지 없는 지 이분탐색

---

★ 26168 배열 전체 탐색하기 ★

import sys
input=sys.stdin.readline

def get1(arr,limit):
    start,end=0,len(arr)-1
    found=False
    while start<=end:
        mid=(start+end)//2
        if arr[mid] < limit:
            start=mid+1
        else: #arr[mid]>=limit
            found=True
            end=mid-1
            ans=mid
    if found:
        return (len(arr)-ans)
    else:
        return 0

def get2(arr,limit):
    start,end=0,len(arr)-1
    found=False
    while start<=end:
        mid=(start+end)//2
        if arr[mid] <= limit:
            start=mid+1
        else: #arr[mid]>=limit
            found=True
            end=mid-1
            ans=mid
    if found:
        return (len(arr)-ans)
    else:
        return 0
    
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for _ in range(m):
    query=list(map(int,input().split()))
    if query[0] == 1:
        limit = query[1]
        print(get1(A,limit))

    elif query[0] == 2:
        limit = query[1]
        print(get2(A,limit))

    else: #query[0] == 3
        limit_1, limit_2 = query[1], query[2]
        print(get1(A,limit_1)-get2(A,limit_2))

 

👩🏼‍🔬 주어진 배열 정렬 뒤, 원하는 숫자보다 크거나 같은 숫자들의 개수 / 원하는 숫자보다 큰 숫자들의 개수를 구할 때는 이분탐색 활용. 경계 index를 구한 뒤, 가장 끝 원소의 index + 1 - 경계 index를 하면 원하는 개수가 나온다. 이 때, 경계 index가 안 구해지는 경우는, 애초에 만족하는 숫자가 없는 경우로 0 리턴. arr[mid]>= target 또는 arr[mid]>target일 때만 답 구할 수 있으므로 이 때만 업데이트

 

👩🏼‍🔬 두 index 사이의 숫자 개수는, 작은 index보다 크거나 같은 숫자의 개수(get1() 함수 활용) 중 큰 index보다 큰 숫자의 개수(get2() 함수 활용)를 빼면 쉽게 구할 수 있다.

---