[개념정리] 이분탐색

요약:
언제 사용??

• 탐색 범위가 넓을 때(입력 값의 범위가 넓을 때) 브루트포스 말고 이진탐색을 사용
• 데이터가 정렬되어 있고 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아야 하는 경우에 사용

기억할 점

• 항상 l와 r이 유의미한 값으로 활용되는 건 아님
  mid값을 구하기 위한 보조 역할일 수 있음
  즉 구하려는 값에 결정적인 영향을 주는 건 mid가 가리키는 값이고, l과 r은 그냥 이 mid를 구하기 위해 보조하는 수준에 그치는 경우도 고려해야함
  말로 하기 조금 애매한데 백준 2467번 용액이나 백준 2110번 공유기설치 풀이를 참고하면 좋을듯

• 주어진 인풋에서 왼쪽 탐색 시 end = mid-1, 오른쪽 탐색 시 start = mid+1

• upper bound, lower bound 소스코드 암기

• start와 end 초기값을 어떻게 설정해야할지 정할 수 있어야함.
  어떤 값을 mid로 두고 어느 조건에서 탐색을 중지하고 해당 mid를 반환해야 하는지 결정해야함.
  어느 조건에서 mid값을 키워서 계속 탐색을 계속할지, 어느 조건에서 mid값을 낮춰서 탐색을 계속할지 정할 수 있어야함
  
  
  ex) 나무 자르기 문제: start를 자를 수 있는 나무의 최소값 1로, end를 가장 큰 나무의 크기로 두고 mid를 나무를 자르는 기준점으로 둠. 잘라진 나무의 나머지가 가져갈려는 나무보다 작으면 mid값을 줄이고 잘라진 나무의 나머지가 가져가려는 나무보다 크면 mid값을 늘림
  숫자탑과 쿼리 문제: 층 수를 구할 때 start를 가장 낮은 층인 1로, end를 가장 높은 층이 될 수 있는 x로 두고 mid를 해당 층이라고 둠. x값이 mid 층보다 낮은 층에 속해있으면 mid값을 줄이고 높은 충에 속해있으면 mid값을 올림

이진탐색 개념

개념

이진 탐색: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함

중간점 인덱스가 가리키는 값인 8보다 찾고자 하는 값인 4가 더 작으므로 중간점 이후는 탐색을 하지 않음

이렇게 단계별로 탐색 범위를 좁힘

시간복잡도

이진 탐색 시간복잡도: O(logN)

소스코드

재귀 함수를 활용한 이진탐색 소스코드

아래는 수도코드

function binary_search(시작점, 끝점):
	# 시작점 > 끝점이면 None 반환
    # 중간점 구함
    
    # if arr[중간점] == 찾고자_하는_값 
    	# 중간점 반환
    
    # if arr[중간점] > 찾고자_하는_값 이면 찾고자 하는 값은 중간점 기준 왼쪽에 있음 
    	# binary_search(시작점, 중간점-1)
        
    # if arr[중간점] < 찾고자_하는_값 이면 찾고자 하는 값은 중간점 기준 오른쪽에 있음
    	# binary_search(중간점+1, 끝점)

반복문을 활용한 이진 탐색 소스코드

아래는 수도코드

while (시작점 <= 끝점):
	# 중간점 구함
    # if arr[중간점] == 찾고자_하는_값 
    	# 중간점 반환
    
    # if arr[중간점] > 찾고자_하는_값 이면 찾고자 하는 값은 중간점 기준 왼쪽에 있음 
    	# 끝점 = 중간점-1
        
    # if arr[중간점] < 찾고자_하는_값 이면 찾고자 하는 값은 중간점 기준 오른쪽에 있음
    	# 시작점 = 중간점+1

lower bound & upper bound

이진탐색은 정렬된 데이터에서 어떤 특정 값이 구하는 알고리즘이다. 여기서 데이터가 중복되는 값이 있으면 lower bound나 upper bound 방식으로 탐색을 진행해야 한다

• lower bound - 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치(인덱스)를 반환.
  즉 정렬된 순서를 유지하면서 배열에 원소를 삽입할 가장 왼쪽 인덱스를 반환
  파이썬에서 bisect_left에 해당함

• upper bound - 데이터 내에서 특정 값보다 처음으로 큰 값이 나오는 위치(인덱스)를 반환.
  즉 정렬된 순서를 유지하면서 배열에 원소를 삽입할 가장 오른쪽 인덱스를 반환
  파이썬에서 bisect_right에 해당함

lower bound(3) -> 3 반환
upper bound(3) -> 6 반환

lower bound 소스코드

찾으려는 target 값이 배열에 없을 때 None return

def lower_bound(arr, target) 
	start = 0
    end = len(arr)
    
    while (start < end):
    	mid = (start + end) // 2
        if (arr[mid] < target):
        	start = mid + 1
        elif (arr[mid] > target):
        	end = mid - 1
        elif (arr[mid] == target):
        	if (end == mid):
            	break
            end = mid
    if (arr[mid] == target):
    	return mid
    else:
    	return None # 못찾음
    

시간복잡도: O(logN)

lower bound는 찾고자 하는 target 값이 처음으로 등장했을 때의 위치를 구하므로 arr[mid] == target이라도 아래와 같은 조건을 추가해주어야 한다

elif (arr[mid] == target):
  if (end == mid):
    break
  end = mid

단, 이 값이 처음으로 나오는 인덱스를 살피는 것이기 때문에 논리상 Right = Mid를 적용하는 것이 맞다. Right = Mid를 적용해두면, 여러 개의 똑같은 값이 나올 때 Right의 값이 점차 왼쪽으로 접근한다. 즉, 이 값이 나오는 가장 처음의 위치를 알 수 있다. 이걸 살짝 응용하면 Left = Mid를 하게 될 경우, Left의 값이 점차 오른쪽으로 접근 하기 때문에 이 값이 나오는 가장 마지막 위치를 알 수 있다.

설명 참고: https://ojt90902.tistory.com/531
위 블로그에 그림으로 잘 설명해두었으니 참고하자

다만 이 방법은 찾으려는 target값이 배열에 없을 때 None을 리턴한다. 때로는 찾으려는 target값이 배열에 없을 때도 target값이 들어가야 할 위치를 리턴해야 되는 경우도 있다.

찾으려는 target 값이 배열에 없을 때도 위치값 return

def lower_bound(arr, target):
	start = 0
    end = len(arr)
    while (start < end):             # start가 end보다 작을 때까지 반복
    	mid = (start + end) // 2
        if (target <= arr[mid]):     # target이 arr[mid] 보다 작거나 같을 때
        	end = mid 				 # end = mid
        else:
        	start = mid+1            # start = mid + 1
   	return start                     # start 반환

start, mid, end가 전부 2가 되면서 while문이 끝나고 start 2가 반환된다

lower bound 수도코드

# start = 0, end = 배열 크기로 지정
# while (start< end) 일 때까지
	# mid = (start+end)//2 로 mid값 구함
    # target이 arr[mid]보다 같거나 작으면 즉, target이 arr[mid]보다 배열 왼쪽에 있으면
    	# end = mid
    # 그렇지 않으면
    	# start = mid+1
    # start 반환
    	

파이썬 bisect_left 소스코드

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

upper bound 소스코드

def upper_bound(arr, target):
	start = 0
    end = len(arr)
    while (start < end):
    	mid = (start + end) // 2
        if (target >= arr[mid]):
        	start = mid + 1
        elif (target < arr[mid]):
        	end = mid
    mid = (start + end) // 2
    if (arr[mid] > target):
    	return mid
    else:
    	return None

arr[mid]가 target과 같은 경우에도 계속 mid를 우측으로 이동시키면서 들어가야 할 위치 중 가장 오른쪽 위치를 반환하도록 한다

참고:
https://ojt90902.tistory.com/531

더 간소화된 코드는 아래와 같다

def upper_bound(arr, target):
	start = 0
    end = len(arr)
    while (start < end):
    	mid = (start + end) // 2
        if (target >= arr[mid]):
        	start = mid + 1 
        else
        	end = mid
    return start

upper bound 수도코드

# start = 0, end = 배열 크기로 지정
# while (start< end) 일 때까지
	# mid = (start+end)//2 로 mid값 구함
    # target이 arr[mid]보다 같거나 크면 즉, target이 arr[mid]보다 배열 오른쪽에 있으면
    	# start = mid + 1
    # 그렇지 않으면
    	# end = mid
    # start 반환

start, end, mid가 전부 3이 되면서 while문이 끝나고 start 3이 반환된다

참고:
https://hee96-story.tistory.com/80
https://duckracoon.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Lower-Bound%EC%99%80-Upper-Bound

파이썬 bisect_right 소스코드

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

파라메트릭 서치 개념

파라메트릭 서치: 최적화 문제를 (여러 번의) 결정 문제로 바꾸어 해결하는 기법
최적화 문제 - 어떤 함수의 값을 최재한 높이거나/낮추는 문제

일반적으로 이진 탐색을 사용하여 해결 가능

이진탐색 문제풀이

문제 1: 떡볶이 떡 만들기

주어진 입력 예시 참고

+) 적어도 6만큼의 떡을 가져가기 위한 높이의 최대값을 구해야 하므로 잘랐을 때 나오는 떡의 길이가 6보다 크면 해당 높이를 따로 기록해두고 최대값 출력

문제 해결 아이디어

탐색 범위가 크기 때문에 브루트포스로 풀면 시간초과가 날 수 있음
이렇게 탐색 범위가 넓을 때는 이진탐색 먼저 고려해봐야함

주어진 예제에서 가장 긴 떡의 길이가 19이기 때문에 끝점을 19로 설정, 중간점은 0과 19의 중간인 9로 설정
이 중간점을 높이라고 간주하고 이걸 기준으로 떡을 자름

수도코드

# 입력받기
# while (start <= end):
	# mid =  (start + end) / 2
    # for i in list: # list에 입력으로 받은 떡의 길이가 들어있음
    	# sum += mid - i
    # if (sum >= 요청한_떡의_길이):
    	# result.append(mid) # 조건에 맞으면 최대값 기록
    	# start = mid + 1
    # else:
    	# end = mid - 1

소스코드

문제 2: 정렬된 배열에서 특정 수의 개수 구하기

문제 해결 아이디어

소스코드

Python 사용 시 bisect 라이브러리를 사용하면 됨

참고:
동빈나님 이코테 강의
https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5