searching

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

순차 탐색

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

Binary Searching

0. time complexity: $O(logN)$
1. ＜ 오름차순으로 미리 정렬(sort)되어 있어야함
2. Find Value 탐색 시작 index를 중앙에서 부터, 시작 idx: list[mid]
   2.1. ${mid=(0+12)/2 = 6}$

단순 binary search

code

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)

이진 탐색을 사용하는 문제

1. 예산

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

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)

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

• Python에서는 bisect 모듈을 따로 제공한다.
  • https://velog.io/@markyang92/python-bisect

bound가 필요한 문제

1. 도약

2. 부분합을 계속 사용하고 UpperBound 사용

• 일명 pNum(부분합)은 계속 sum() 함수를 사용하지 말고 element를 넣었다 뺐다해서 구하자! 시간 아깝다.
•