이진 탐색 알고리즘

이진 탐색과 순차 탐색이 있다

이진 탐색 동작 예시

이렇게 중간부터 시작해서 쪼개나가며 찾아나가는 과정이다.

이진 탐색의 시간 복잡도

이진 탐색 소스코드

재귀적 구현

def bs(arr,target,start,end):
    if start>end:
        return None
    mid = (start+end)//2 
    if arr[mid]==target:
        return mid 
    elif arr[mid]>target:
        return bs(arr,target,start,mid-1) 
    else :
        return bs(arr,target,mid+1,end)

n,target = list(map(int,input().split()))

arr = list(map(int,input().split()))

result = bs(arr,target,0,n-1)
if result==None:
    print("원소X")
else:
    print(result+1)

반복문 구현

def bs(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 None

n,target = list(map(int,input().split()))

arr = list(map(int,input().split()))

result = bs(arr,target,0,n-1)
if result==None:
    print("원소X")
else:
    print(result+1)

파이썬 이진 탐색 라이브러리

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right 

def count_by_range(a,left_value,right_value):
    right_idx = bisect_right(a,right_value)
    left_idx = bisect_left(a,left_value)
    return right_idx - left_idx 

a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력 
print(count_by_range(a,4,4)) # 2

# -1~3범위에 있는 데이터 개수 출력 
print(count_by_range(a,-1,3)) @6

파라메트릭 서치

이진 탐색 예제

떡볶이 떡 만들기

문제 해결 아이디어

탐색범위가 겁나 많을때 단순히 선형탐색으로 하게 된다면 시간초과를 받을 수 있으니 이진탐색을 떠오르자 !

이와같이 시작점과 끝점의 위치를 바꿔가며 찾아나가는 것이다.

답

n,m = map(int,input().split())
arr = list(map(int,input().split()))

start = 0 ; end = max(arr)

result=0
while start<=end:
        total = 0
        mid =(start+end)//2 
        for x in arr: #떡 자른 양 계산하기 
            if x> mid:
                total += x -mid 
        # 떡 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
        if total<m:
            end = mid - 1 
        # 떡 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
        else : 
            result = mid  #최대한 덜 잘랐을때가 답이므로 기록계속 갱신 
            start = mid + 1

print(result)

정렬된 배열에서 특정 수의 개수 구하기

아마 bisect..!?

문제 해결 아이디어

답

from bisect import bisect_left, bisect_right 

def count_by_range(a,left_value,right_value):
    right_idx = bisect_right(a,right_value)
    left_idx = bisect_left(a,left_value)
    return right_idx - left_idx 

n,x = map(int,input().split())
arr = list(map(int,input().split())) 

# 값이 4인 데이터 개수 출력 
result = count_by_range(arr,x,x)
print(result if result else -1)

오호..! bisect 신기방구