[Algorithm] 이분 탐색 - 심화

이분 탐색을 활용한 Parametric Search 문제에서 정말 다양한 코드들이 존재한다. 

우선 종료 조건에 따라,  st < en과 st <= en으로 분리된다. 

 

또한, 구간 업데이트 시, st = mid + 1, st = mid 혹은 en = mid - 1, en = mid 과 같은 다양한 코드들을 마주하게 된다.

이들의 조합을 생각해 보면 정말 수많은 조합이 가능해진다.

 

실제로 PS에서 이런 종료 조건들에 의해 답이 틀리는 경우도 있었으며, 무한 루프에 빠지는 경험을 자주 하곤 했다. 

이에 따라 이들의 차이점에 대해 정리하고자 한다.

아래의 나오는 코드들은 Swift로 작성되었다. 

 

이분 탐색

"이분 탐색"은 정렬되어 있는 원소들에서 탐색 범위를 절반으로 줄여가며 탐색하는 알고리즘이다.

func binarySearch<T: Comparable>(elements: [T], target: T) -> Int? {
  var st = 0
  var en = elements.count - 1
  
  while st <= en {
    let mid = (st + en) / 2
    
    if elements[mid] == target {
      return mid
    } else if elements[mid] > target {
      en = mid - 1
    } else {
      st = mid + 1
    }
  }
  
  return nil
}

 

이때의 핵심은 탐색의 범위를 반씩 줄여간다는 것이다. 

예를 들어, [st, en]의 범위에서 mid가 작거나 크다면, 

mid를 포함한 나머지 구간은 탐색에서 제외시켜 버린다. 

 

이렇게 매 횟수마다 절반씩 줄여나가기 때문에, 시간복잡도는 $O(logN)$이 된다.

 

Parametric Search 

“Parametric Search”란 특정 조건을 만족하는 값 중 최적값을 찾는 알고리즘이다.

이분 탐색에서는 특정 조건을 만족하는 값을 찾는 문제인 반면, 파라메트릭 서치는 이 중 최적값을 찾는 문제이다. 

 

파라메트릭 서치의 핵심은 최적화 문제를 결정 문제로 바꾸어 푼다는 점이다.

• 최적화 문제: 가능한 해 중 가장 최적의 해를 찾는 것 (3보다 큰 최초의 수)
• 결정 문제: 주어진 조건에 해가 존재하는지 여부를 판단하는 것 (3보다 작다 크다.)

예를 들어, [1, 2, 3, 4, 4, 4, 5] 의 배열에서 최초의 4가 등장하는 인덱스를 찾는다고 가정해 보자. 

이를 결정 문제로 바꾸게 되면, "k번째 인덱스가 4보다 큰가?"라는 문제로 바뀌게 된다. 

이 K에 대해서 이분 탐색으로 바꿔서 풀게 되면 결정문제로 해를 구할 수 있게 된다. 

 

Parametric Search는 이분 탐색과 다르게 원하는 조건과 동일한 값이 나오더라도, 

최적해를 구하는 문제이기 때문에, 해가 아닐 수 있다. 

위의 예시에서 5번 인덱스의 4를 먼저 발견했다고 해서, 최초의 4를 보장할 수 없듯이 말이다.

 

이러한 Parametric Search를 활용하는 대표적인 것에는 lowerBound, upperBound 등등 이 있다. 

 

구간의 범위 

Parametric Search문제에서는 구간을 어떻게 설정하느냐에 따라, 종료 조건 혹은 탐색의 범위를 줄여나가는 방식에 차이가 있을 수 있다. 

이러한 구간에는 다음과 같은 방법들이 존재한다. 

• 닫힌 구간: [st, en]
• 반열린 구간: [st, en)
• 열린 구간: (st, en)

대부분 닫힌 구간, 반열린 구간을 많이 사용하기에 해당 포스팅에선 2가지 방식만 다룰 것이다. 

아래 사용하는 예시들은 lowerBound를 기준으로 코드를 작성했다. 

 

닫힌 구간

닫힌 구간에서의 코드를 우선적으로 살펴보자.

func lowerBound<T: Comparable>(elements: [T], target: T) -> Int {
  var st = 0
  var en = elements.count - 1
  
  while st <= en {
    let mid = (st + en) / 2
    
    if elements[mid] < target {
      st = mid + 1
    } else {
      en = mid - 1
    }
  }
  
  return st
}

닫힌 구간이기 때문에, mid를 기준으로 다음과 같이 2개의 닫힌 구간으로 분할된다.

• [st, mid]
• [mid, en]

이분 탐색과 마찬가지로, mid에서의 탐색을 한 후, 다음 탐색에선 mid를 제외시켜 버리게 된다. 

따라서, 아래와 같이 업데이트 되어야 한다. 

• [st, mid - 1]: en = mid - 1로 업데이트
• [mid + 1, en]: st = mid + 1로 업데이트

 

종료 조건

닫힌 구간에서 종료 조건은 다음과 같다. 

while st <= en

이는, 닫힌 구간이기에, [k, k]의 범위에서도 k라는 숫자가 존재한다. 즉, 검사해주어야 하는 숫자가 존재한다. 

 

또한, 탐색의 끝 값도 유효한 해가 될 수 있기에 검사를 해주어야 한다. 

 

 

주의할 점 

닫힌 구간에서 주의할 점은 탐색이 종료된 후, st != en 이 된다.

따라서, 문제 조건에 맞게 st를 리턴할지, en을 리턴할지 혹은 st - 1, en -1을 리턴할지 고려해야 한다. 

 

예를 들면 lowerBound의 경우에는 st를 리턴했던 반면, upperBound에서는 en을 리턴해야 한다. 

func upperBound<T: Comparable>(elements: [T], target: T) -> Int {
  var st = 0
  var en = elements.count - 1
  
  while st <= en {
    let mid = (st + en) / 2
    
    if elements[mid] <= target {
      st = mid + 1
    } else {
      en = mid - 1
    }
  }
  
  return en
}

 

반열린 구간

func lowerBound<T: Comparable>(elements: [T], target: T) -> Int {
  var st = 0
  var en = elements.count
  
  while st < en {
    let mid = (st + en) / 2
    
    if elements[mid] < target {
      st = mid + 1
    } else {
      en = mid
    }
  }
  
  return en
}

 

가장 큰 특징으로는 반열린 구간이기에, en = elements.count로 설정해주었다.

 

반열린 구간에서는 [st, en)이 mid값을 기준으로 다음과 같이 2개의 열린구간으로 분할된다.

• [st, mid)
• [mid, en)

 

반열린 구간 역시 이분 탐색과 마찬가지로, mid 검사 이후 다음 탐색에서 mid는 구간에서 제외되어야 한다. 

이로 인해, 다음 범위는 다음과 같이 설정된다. 

• [st, mid): en = mid 로 업데이트  
• [mid + 1, en): st = mid + 1로 업데이트, mid를 제외시켜야 하기 때문에 위와 같이 업데이트한다.

 

종료 조건 

반열린 구간에서의 종료 조건은 다음과 같다. 

while st < en

 

이는 [k, k)를 만족하는 자연수 k는 존재하지 않는다. 따라서, 두 값이 같을 때의 별도의 탐색을 필요 없게 된다. 

 

반열린 구간의 장점은 탐색 종료 시에는 st == en이기 때문에 어떠한 값을 리턴해도 상관없다는 장점이 있다.