[샛길공부] 이진탐색(이분탐색) 문제풀기 (feat. 이코테 유튜브강의)

이진탐색(이분탐색) 개념에 대해 정리한 글은

아래 클릭👇👇

https://coding-nurse.tistory.com/41

---

* 강의 채널 : 동빈나

* 강의 이름 : (이코테 2021 강의 몰아보기) 5. 이진탐색

* 강의 링크 : https://youtu.be/94RC-DsGMLo

 

12분30초부터~ 문제풀이 시작!

---

 🎀 이진 탐색 문제풀기 

n,m = map(int,input().split())
array= list(map(int,input().split()))
 
start = 0
end = max(array)
 
result=0    #최적값 후보변수
 
while start<=end:
    mid=(start+end)//2
        
    cut=0    #자른 떡들계산 변수
        
    # 떡 잘랐을때 양 계산/ 떡 자르기조건: 떡이 중간점보다 커야함
    for i in array:
        if i > mid:
            cut += i-mid
        
    # 1) 잘라나온 떡이 조금
    if cut< m:
        end = mid - 1
        
    # 2) 잘라나온 떡이 많음
    else:
        result = mid    #최적값후보로 등록
        start = mid + 1
 
print(result)

---

 🎀 이진 탐색 라이브러리 문제풀기

bisec_rigtht 값에서 bisec_left 값을 빼서 특정 범위 안에 속하는 데이터 개수를 구하는데 유용했던 것을 기억하면서!

 

n,x = map(int, input().split())
array=list(map(int, input().split()))
 
from bisect import bisect_left, bisect_right
 
def count(array, left_v, right_v):
    left_ind = bisect_left(array, left_v)
    right_ind = bisect_right(array, right_v)
    return right_ind - left_ind
 
#결과값
result = count(array,x,x)
 
#없으면 -1출력
if result == 0:
    print(-1)
#있으면 갯수 출력
else:
    print(result)

---

 

🧐공부 한줄 평 : 이진 탐색 문제를 이제 풀어보쟈