이분 탐색(Binary Search)

이분 탐색이란? 

정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제며,

검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.

 

더 자세히 말하자면 

정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다

---

아직 말로는 잘 모를 수 있다.

그림으로 이해해보자. 위에는 우리가 할 이분 탐색, 아래는 순차적으로 탐색이다.

(이진 탐색의 시간 복잡도는 O(logN)  전수 조사하는 O(N))

정렬된 리스트에서 중앙값이 찾고자하는 값보다 작거나 큰지에 대하여 범위가 수정되어 

다시금 찾는 방식이다. 

 

그럼 이분탐색이 오로지 숫자를 이렇게 찾는 방식으로 끝나는 알고리즘이라면 구현만으로 쉬운 문제가 아닌가?

그렇지ㅋ 않ㅋ다 ㅋ

 

이분탐색만으로 저렇게 쉽게 원하는 숫자를 찾는 문제는 많지않다. 

대부분은 당장에 답을 찾기보단 해당 범위에서 띄엄띄엄 접근하여 최적 값을 구하기 위해 많이 사용한다.

(말이 띄엄띄엄이지 어떠한 범위가 접근할 필요가 없음을 알면 해당 범위만큼 제외하고 다른 것들을 접근하는 엄청나게 효율적인 접근방식이다...완전 탐색은 모든걸 돈다)  

 

그럼 이 문제를 통해 이분탐색의 감을 익혀보자 

 

2805번: 나무 자르기

나무를 어느 정도 자르냐에 따라 sum의 값이 변하는데 1부터 가장 긴 나무의 길이만큼 하나씩 연산하여

접근하기 보다는 중앙에서 가능과 불가능의 범위를 찾아 가장 적절한 최대값을 찾을 수 있다. 

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
tree = list(map(int,input().split()))

def sum_tree(center):
    temp_return = 0
    for i in tree:
        if i >=center:
            temp_return += i - center
    return temp_return

start = 0
end = max(tree)
result = 0

while start <= end:
    mid = (end+start)//2
    temp = sum_tree(mid) 
    if temp >= m:
        if result<mid:
            result = mid
        start = mid +1
    else:
        end = mid - 1
print(result)

 

 

이미지참고)https://tenor.com/view/binary-search-sequence-search-gif-20595028