이진탐색(Binary Search)

1. 이진탐색

: 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 

=> 탐색 범위가 크다면 이진탐색 떠올리기!

 

(1) 이진탐색의 기본 틀 

• start<=end인 경우에만 탐색 수행 가능 (start=end=mid인 경우도 존재해서)
• mid = (start+end)//2
• 리스트 인덱스 mid의 값과 target(찾고자 하는 숫자)을 비교하여 탐색범위 재결정

EX) 떡볶이 떡 만들기

=> 일단 절단기의 높이를 최대한 높게 하는 것이 목표이기 때문에 start=0, end=떡의 길이를 저장한 리스트에서 최대값으로 설정

=> 계속해서 start를 mid+1에 설정하며 절단기의 높이를 높여도 조건 충족하는지 확인한다

=> 이때 요청한 떡의 길이 M보다 작아진다면 end = mid-1로 하여 왼쪽으로 절단기의 높이를 다시 늘린다 

def Binary_Search(tteok, M, start, end):
    #탐색범위가 크다 ! => 이진 탐색 생각
    
    while(start<=end):
        mid = (start+end)//2
        sum=0
        for i in range(4):
            if(tteok[i]>mid):
                sum+=(tteok[i]-mid)
        if(sum>=M):
            res= mid
            start = mid+1
        else:
            end = mid-1

    return res    

def main():
    #N: 떡의 갯수, M: 요청한 떡의 길이
    N,M = map(int, input().split())
    tteok = list(map(int, input().split()))

    print( Binary_Search(tteok,M, 0, max(tteok)))


if __name__=="__main__":
    main()

 

1-1. 이진 탐색 라이브러리

: 아래의 모듈 이용 

from bisect import bisect_left, bisect_right 

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

x in list : 해당 인덱스 반환
x not in list : 삽입할 위치의 인덱스 반환 (가장 왼쪽)

• bisect_right(a,x) : 정렬된 순서 유지하면서 배열 a에 x 삽입할 가장 오른쪽 인덱스 반환

x in list : 해당 인덱스 반환
x not in list :  삽입할 위치의 인덱스 반환 (가장 오른쪽)

=> 값이 n인 데이터의 개수 출력할 수 있다

=> 값이 [a,b] 범위에 있는 데이터의 개수 출력할 수 있다

from bisect import bisect_left, bisect_right


def main():
    array=[1,2,4,4,8]
    left = bisect_left(array, 4)
    right = bisect_right(array,4)
    print(right-left)



if __name__=="__main__":
    main()