[Algorithm 문제 유형 분석] binary search(이진탐색) 쉽게 구현하기

난 재귀를 극혐하므로 가능하면 반복으로 구현한다...

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0 
right = length-1

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

 

[문제 유형]

가장 흔한건

숫자가 존재하는지 여부 찾기 

나무, 전선 자르기: min을 0으로, max를 리스트의 최대값으로 잡고 점점 좁혀나간다. 

 

조금 번외인건

공유기 설치 - 주어진 개수만큼의 공유기를 최대한 거리 멀게 설치하는 유형. 거리를 min을 0으로, max를 리스트의 최대값으로 잡고 점점 좁혀나간다. 

 

K번째 수 같이 이진탐색인지 파악하기 어려운 유형도 있다. 

배수인 점을 이용해서 count를 파악하고 binary search를 하면 됐던 유형이다. 

 

 

 

 

 

 

 

 

 

[출처]

https://velog.io/@madfinger/Binary-Search이진-탐색-파이썬