Awesome

https://www.acmicpc.net/problem/10816

참고) 파이썬에서 이 문제를 이분탐색으로 풀면 시간초과가 발생한다.

import sys
 
 
# 처음으로 key와 같거나 큰 값이 나타나는 위치를 찾는다
def lowerBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            end = mid
        elif nList[mid] < key:
            start = mid + 1
    return end
 
 
# 처음으로 key보다 큰 값이 나타나는 위치를 찾는다
def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            start = mid + 1
        elif key < nList[mid]:
            end = mid
    return end
 
 
n = int(sys.stdin.readline())
nList = list(map(int, sys.stdin.readline().split()))  # 상근이 갖고 있는 카드 리스트
m = int(sys.stdin.readline())
mList = list(map(int, sys.stdin.readline().split()))  # 찾아야 할 카드 리스트
nList.sort()
 
for i in mList:
    ret = upperBound(0, n, i) - lowerBound(0, n, i)
    print(ret, end=' ')

앞서 Lower bound 이진 탐색에 대해 알아보았다. 

https://awesomeroo.tistory.com/30

이번에는 Upper bound 이진 탐색이다. Upper bound 이진 탐색은 처음으로 큰 값이 나타나는 위치를 찾는다.

먼저 일반적인 binary search 코드이다.

Lower bound에서도 그랬지만, Upper bound와의 코드 비교를 위해서 올린다.

def binarySearch(start, end, key):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > key:
            end = mid - 1
        elif lst[mid] < key:
            start = mid + 1
        elif lst[mid] == key:
            return 1
    return 0
 
 
lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(binarySearch(0, len(lst)-1, 3))

그리고 Upper bound binary search.

def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if lst[mid] == key:
            start = mid + 1
        elif lst[mid] < key:
            start = mid + 1
        elif key < lst[mid]:
            end = mid
    return end
    
lst = [0, 1, 2, 3, 3, 5, 6, 7, 8]
print(upperBound(0, len(lst), 6))

이번에도 upper bound에서는 일반 바이너리 서치와 같은 세 가지 if문이 등장한다.

1. lst[mid] == key

2. lst[mid] < key

3. key < lst[mid]

먼저 1번을 보자. upper bound는 key보다 큰 값이 나오는 위치를 찾아야 하므로, 

lst[mid]가 key와 같다면 그 값은 포함시킬 필요가 없다. 따라서 start를 mid에서 하나 증가한 값으로 변경한다.

2번. key가 lst[mid]보다 크다면, 마찬가지로 key보다 큰 값을 찾아야 하기 때문에 key보다 작은 lst[mid]는 다음 탐색 범위에 포함시킬 필요가 없다. 그래서 start를 mid에서 하나 증가한 값으로 변경한다.

3번. key가 lst[mid]보다 작을 때를 보자. mid가 너무 큰 것이므로 end를 작게 해줘야 하는데, lst[mid]가 key보다 처음으로 큰 값(원하는 값)일 수도 있으므로 lst[mid]를 포함시키기 위해 end=mid가 된다.

return end 하는 이유는, start = end가 되는 순간 start와 end가 정답이 되기 때문이다.

또한 함수를 처음 콜하는 부분에서 end가 len(lst)-1이 아니라 len(lst)가 되는 이유는,

리스트를 끝까지 살폈는데 답이 안 나온다면 마지막으로 살폈던 위치를 반환할 것이기 때문이다. 그 때 len(lst)를 반환해서 답이 없음을 알아보기 위함이다. 

먼저 이진 탐색 코드.

def binarySearch(start, end, key):
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > key:
            end = mid - 1
        elif lst[mid] < key:
            start = mid + 1
        elif lst[mid] == key:
            return 1
    return 0
    
lst = [0, 1, 2, 3, 3, 5, 6, 7]
print(binarySearch(0, len(lst)-1, 7))

Lower bound 이진 탐색이란 

찾고 싶은 key 값과 같은 값이 나타나는 첫 위치를  찾거나,

같은 값이 없으면 큰 값이 나타나는 첫 위치를 찾는 방법이다.

def lowerBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if lst[mid] == key:
            end = mid
        elif key < lst[mid]:
            end = mid
        elif lst[mid] < key:
            start = mid + 1
    return end
    
lst = [0, 1, 2, 3, 3, 5, 6, 7]
print(lowerBound(0, len(lst), 7))

범위 설정에 있어서 이진 탐색과 비교했을 때 이해가 안되서 애먹었다.

일부러 이해하기 쉽도록 ==, <, > 세 가지 케이스로 나누었다.

먼저 2번째 줄, 보통의 이진 탐색은 조건을 while start <= end 로 잡는다.

하지만 lower bound는 while start < end 로 잡는다.

그 이유는 일반 이진 탐색은 start == end가 되었을 때도 그 값이 찾고자 하는 key였는지 살피고 나서 찾았으면 1을 리턴하고 못 찾았으면 0을 리턴하든지 해야 하는데,

lower bound는 start == end가 되었으면 바로 그 위치를 리턴하면 되기 때문이다. start == end가 되는 순간 그 값이 key와 같은 값이거나 처음으로 큰 것이 나타나는 위치이기 때문이다. 그래서 start == end 는 while이 진행될 조건으로 포함시킬 필요가 없다.

다음 if 문을 보자.

일반 이진 탐색에서의 세 가지 if문을 보자.

1. lst[mid] == key

2. key < lst[mid]

3. lst[mid] < key

먼저 3번은 일반 이진 탐색과 같다고 보면 된다. 

lower bound는 key와 같거나 더 큰 값을 찾아야 하므로 key가 더 크다면 start를 높여서 최소한 같은 값이라도 찾을 수 있도록 범위를 좁혀주어야 한다.

하지만 1. lst[mid] == key 일 때는?

원하는 key가 나오긴 했지만, 똑같은 값이 더 왼쪽에서 나타날 수도 있다.

따라서 이 위치를 포함해서 더 작은 위치에서 이 값이 등장하지는 않는지 다시 한번 살펴야 하는 것이다.

2. key < lst[mid]도 마찬가지이다. key가 lst[mid]보다 작긴 하지만, 무작정 바이너리 서치처럼 end = mid - 1 할 수 없는 이유는 lst[mid]가 key보다 처음으로 큰 값일 수 있기 때문이다.

마지막, lowerBound 함수를 호출하는 부분을 보자.

보통 이진 탐색이라면 함수를 호출할 때 start를 0으로, end를 len(lst)-1로 둘 것이다. 왜냐? 배열은 0부터 시작이니까.

하지만 lower bound 이진 탐색의 경우, end를 len(lst)로 두었다.

그 이유는 리스트 안에 원하는 값이 없었을 경우, 즉 원하는 key보다 작은 값들만 있었을 경우 

마지막 while문을 돌 때 start와 end가 len(lst)가 됨으로써

len(lst)를 반환하게 되고, 리스트에 존재하지 않는 인덱스를 반환했기 때문에 리스트에 key가 없다! 는 것을 알기 위함이다.

(원하는 key보다 큰 값들만 있었을 경우에 리턴값은 0이다. lower bound가 뭔지 생각해보자)

https://www.acmicpc.net/problem/1920

import sys
 
 
def binarySearch(start, end, num):
    mid = (start + end) // 2
    if nList[mid] == num:
        return 1
    if start > end:
        return 0
    if num > nList[mid]:
        start = mid + 1
    elif num < nList[mid]:
        end = mid - 1
    return binarySearch(start, end, num)
 
 
n = int(sys.stdin.readline())
nList = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
mList = list(map(int, sys.stdin.readline().split()))
 
nList.sort()
 
for i in mList:
    print(binarySearch(0, n-1, i))