[algorithm] 탐색, Searching, Lower, Upper bound

markyang92·2021년 10월 13일

algorithm

목록 보기

5/13

searching

sorting은 오름차순이냐, 내림차순이냐로 정렬하는 것
searching(탐색)은 내가 선택한 값이 List에 어디에 있는지 탐색하는 것

순차 탐색

time complexity: ${O(N)}$
＜ 오름차순으로 미리 정렬(sort)되어 있어야함
index를 순차로 훑으며, 순차 탐색
2.1. 최적 조건: Find Value가 idx: 0에 존재하는 경우
2.2. 최악 조건: Find Value가 idx: len(list)-1에 존재하는 경우
2.3. 없는 경우: Find Value가 list에서 순차탐색 '중' 아직 못 찾고, 더 큰 값이 있는 경우

Binary Searching

time complexity: $O(logN)$
＜ 오름차순으로 미리 정렬(sort)되어 있어야함
Find Value 탐색 시작 index를 중앙에서 부터, 시작 idx: list[mid]
2.1. ${mid=(0+12)/2 = 6}$
2.2. Value: A[mid] = '23' ＜ Find Value : 오른쪽 정렬
2.3. Find Value ＜ Value: A[mid] = '23' : 왼쪽만 정렬
2.4. 비교시 마다 탐색 범위가 ${½}$

단순 binary search

python

import sys

A=[0]

def binary_search(left:int, right:int, value:int):
    if left>right:
        return -1 # 못찾은 경우
    mid=int((right+left)/2)
    if A[mid] < value:
        return binary_search(mid+1,right,value)
    elif A[mid] == value:
        return mid # 찾은 경우 배열내 idx 리턴
    elif value < A[mid]:
        return binary_search(left,mid-1,value)

c++

binary search

이진 탐색을 사용하는 문제

1. 예산

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

배열 내 값이 아닌, '아직 모르는 값'을 위해 이진 탐색을 할 때는, 그냥 이진 탐색 코드를 사용하자.

python

def bin_search(l: int, r: int):
    if l>r:
        return
    m=(l+r)//2
    "여기서 구한 m" 값으로 예산 문제를 구해본다.
    res=budget(m)
    
    
    if res == lower:
        bin_search(l, m-1)
    elif res == upper:
        bin_search(m+1, r)

if __name__ == '__main__':
    bin_search(0,150)

c++

count

binary search를 이용하는 count (중복 포함)

code

import sys

N=None
A=[-1]
M=None
F=[-1]

def count(start,value,cnt):
    for i in range(start,-1,-1):
        if A[i] == value:
            cnt+=1
        else:
            break
    for i in range(start+1,N):
        if A[i] == value:
            cnt+=1
        else:
            break
    return cnt

def binary_search(left: int, right:int, value: int):
    if left>right:
        return 0
    mid=int((left+right)/2)
    if A[mid] < value:
        return binary_search(mid+1,right,value)
    elif A[mid] == value:
        return count(mid,value,0)
    elif value < A[mid]:
        return binary_search(left,mid-1,value)

if __name__ == '__main__':
    readl=sys.stdin.readline
    N=int(readl())
    A=list(map(int,readl().split()))
    M=int(readl())
    F=list(map(int,readl().split()))
    for i in range(0,M):
        print(binary_search(0,N-1,F[i]))

Bound

Binary Search 로 반드시 value를 찾는 것이 아닌, 배열내 근사치 및 lower bound, upper bound를 지정해 몇개가 있는지 세는지 등에서도 사용 가능하다.
- 전제 조건: 당연히 sort 상태

자신의 입맛에 맞게 lower bound, upper bound를 지정하자.
- lower bound: 9 이상 의 가장 가까운 작은 값
- upper bound: 13 이하 의 가장 가까운 작은 값

이진 탐색을 통해 $O(N)$ 을 $O(logN)$ 으로 줄일 수 있다.

lower bound

arr=[]
def lower_bound(val: int):
    global arr
    l=0
    r=len(arr)
    while l<r:
        mid=l+(r-l)//2
        if arr[mid] < val:
            l=mid+1
        else:
            r=mid
    return r

upper bound

arr=[]
def upper_bound(val: int):
    global arr
    l=0
    r=len(arr)
    while l<r:
        mid=l+(r-l)//2
        if arr[mid]<=val:
            l=mid+1
        else:
            r=mid
    return r

실사용


arr=[]
def lower_bound(val: int):
    global arr
    l=0
    r=len(arr)
    while l<r:
        mid=l+(r-l)//2
        if arr[mid] < val:
            l=mid+1
        else:
            r=mid
    return r

def upper_bound(val: int):
    global arr
    l=0
    r=len(arr)
    while l<r:
        mid=l+(r-l)//2
        if arr[mid]<=val:
            l=mid+1
        else:
            r=mid
    return r


if __name__ == '__main__':
    #    0,1,2,3,4,5,6,7,8, ....             18
    arr=[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,6,6]
    print(lower_bound(3)) # 8
    print(upper_bound(5)) # 18


    #    0,1,2,3,4,5,6,7,8, ....       15,16
    arr=[1,1,1,1,2,2,2,2,4,4,4,6,6,6,6,6]
    print(lower_bound(3)) # 8
    print(upper_bound(7)) # 16