이진 탐색 & 매개변수 탐색

이진 탐색 (Binary Search)

이진(이분) 탐색이란 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법이다.
배열 내부의 데이터가 정렬되어 있어야 사용 가능한 알고리즘이다.
탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.
- 변수 3개 = 시작점, 끝점, 중간점
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는다.

🔎 결정 문제란?

답이 True or False인 문제를 의미하며 보통 1개의 parameter를 가짐

이진 탐색 동작 과정

1단계

시작점과 끝점을 확인한 후 중간점을 정한다.
- 중간점이 실수라면 소수점 이하를 버린다.
중간점[4]의 데이터와 찾으려는 데이터 4를 비교한다.
- 중간점의 데이터가 더 크므로(8) 확인할 필요없이 끝점을 [4] 이전의 [3]으로 옮긴다.

2단계

시작점[0]과 끝점[3]의 중간점[1]을 구한다.
- 중간점에 위치한 데이터 2 는 찾으려는 데이터 4보다 작으므로 중간점 이하의 데이터는 확인할 필요가 없다
- 시작점을 [2]로 변경한다.

3단계

시작점[2]과 끝점[3]의 중간점[2]을 구한다.
중간점에 위치한 데이터와 찾으려는 데이터가 동일하므로 현 시점에서 탐색을 종료한다.

👉 전체 데이터는 10개이지만 이진 탐색을 이용하면 총 3번의 탐색으로 원소를 찾을 수 있다.
• 한번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다.
• 시간 복잡도 : O(logN)

👉 결정 문제의 답은 항상 F~T 분포가 아니라 T~F 분포일 수도 있다. 또한 정답은 경계의 왼쪽(=lo)일 수도 있고 오른쪽(=hi)일 수도 있다. 따라서 결정 문제의 분포와 정답이 lo인지 hi인지는 문제별로 잘 생각해줘야 한다.

재귀함수로 구현

def binary_search(array, target, start, end):
  if start > end:
    return None

  mid = (start + end) // 2

  if array[mid] == target:
    return mid
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  elif array[mid] < target:
    return binary_search(array, target, mid + 1, end)


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

result = binary_search(array, target, 0, n - 1)
if result is None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

반복문으로 구현

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2

    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return None


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

result = binary_search(array, target, 0, n - 1)
if result is None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

Lower Bound & Upper Bound

Lower bound는 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해준다.

파이썬 bisect 모듈의 bisect_left

def bisect_left(a, x, lo=0, hi=None):
    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는 특정 값보다 처음으로 큰 값이나 나오는 위치를 리턴해준다.

파이썬 bisect 모듈의 bisect_right

def bisect_right(a, x, lo=0, hi=None):
    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. 해당 값이 리스트에 있을 때

bisect_right - 해당 index+1 반환

bisect_left - 해당 index 반환

from bisect import bisect_right, bisect_left

lst= [1, 4, 6, 10]

print(bisect_left(lst, 6)) # result = 2
print(bisect_right(lst , 6)) # result = 3

2. 해당 값이 리스트에 없을 때

bisect_right - 리스트 오름차순에 들어갈 index 반환

bisect_left - 리스트 오름차순에 들어갈 index 반환

print(bisect_left(lst, 9)) # result = 3
print(bisect_right(lst , 9)) # result = 3

매개변수 탐색

최적화 문제를 결정 문제로 풀 수 있는 기술

🔎 최적화 문제 👉 어떤 알고리즘의 최적의 솔루션을 찾아내는 것

결정 문제 👉 답이 이미 결정되어있다고 보고 문제를 푸는 것

매개 변수 탐색 문제를 언제 사용할 수 있을까?

결정 문제로 풀 수 있는 문제
어떤 시점까지는 조건을 만족하지만, 그 시점 이후로는 조건을 만족하지 않는 경우에서 최댓값 찾기 (Upper Bound)
어떤 시점까지는 조건을 만족하지 않지만, 그 시점 이후로는 조건을 만족하는 경우에서 최소값 찾기 (Lower Bound)

매개 변수 탐색의 동작 과정

문제에서 최종적으로 찾고자하는 최솟값/최댓값을 매개변수로 본다.
결정 함수를 정의하고 구현했을 때 결과 배열이 연속인지 확인한다.
최솟값이면 결정 함수의 결과가 [f,f,...,t,t] 에서 f->t 로 바뀌는 부분을 찾는다.
최댓값이면 결정 함수의 결과가 [t,t,...,f,f] 에서 t->f 로 바뀌는 부분을 찾는다.

이진 탐색과의 차이점

이진 탐색 👉 target과 일치한 값을 찾으면, 함수를 종료하고 위치 반환
매개 변수 탐색 👉 target과 일치하는 값을 찾아도 함수를 종료하지 않고 더이상 탐색할 배열이 남아있지 않을 때까지 탐색을 계속한다.

매개 변수 구간 정의

def binary_search(arr,lo,hi,value):
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= value:
          lo = mid
        else:
          hi = mid
    return arr[lo]

조건 lo + 1 < hi 👉 반복문 내에서 arr[lo] < arr[hi]가 항상 성립한다.

lo와 hi가 1씩 차이가 날 경우 (hi-lo == 1)
- arr[lo] < arr[hi]가 성립하지 않을 수 있지만
- 👉 mid <=hi 또는 lo <= mid 가 되어
lo와 hi가 1이상 차이 날 경우 (hi-lo > 1)
- 👉 arr[lo] < arr[hi] 식은 불변식이 된다.
값을 찾는 조건에 따라 lo 또는 hi가 정답이 된다
- 조건 arr[mid] <= value 👉 arr[lo] == value 이다.
- 조건 arr[mid] < value 👉 arr[hi] == value 이다.
lo, hi 구간을 정의 👉 lo = 구간의 최솟값 -1 & hi = 구간의 최댓값
- lo = 구간의 최솟값 으로 정의할 경우, hi는 구간의 최솟값이 될 수 없다.(lo + 1 < hi)