04. 이진탐색

1. 이진탐색

기본 아이디어

찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복합니다. 이때, 찾는 범위 속 원소의 갯수가 1개로 줄어들면 탐색을 종료합니다.

이진탐색을 위해서 배열에 들어있는 값은 반드시 정렬되어 있어야 합니다.

 

상세 과정

• left ≤ right를 만족할때까지(원소 수가 1개로 줄어들 때까지), 찾는 숫자인 target과 가운데 위치(mid)에 해당하는 값인 arr[mid]를 비교합니다.
  • target == arr[mid]인 경우 : 해당 위치인 mid를 반환합니다.
  • target < arr[mid]인 경우 : right를 mid-1로 움직입니다.
  • target > arr[mid]인 경우 : left를 mid+1로 움직입니다.
• 반복이 끝났는데도 아직 target의 위치가 반환되지 않았다면, 찾는 숫자인 target이 없다는 표시인 -1을 반환합니다.

 

시간복잡도

이진탐색은 반드시 정렬이 되어야함을 전제로 합니다. 루프를 한 번 돌때마다 구간의 길이는 반으로 감소하고, 구간의 길이가 1이 될때까지 계속 반복합니다. 즉, 루프는 약 logN번 돌게 되므로, 시간복잡도는 O(logN)입니다.

• 정렬이 되어 있는 경우
  • 탐색의 시간복잡도는 O(logN)입니다.
  • 순차탐색의 시간복잡도 O(N)과 비교할 때 엄청 빠르므로, 기본적으로 정렬이 된 경우엔 값을 찾을 때 이진탐색을 많이 사용합니다.
• 정렬이 되어 있지 않은 경우
  • 정렬을 하는 데 O(NlogN)의 시간이 소요됩니다. (ex. 퀵 정렬)
  • 탐색을 하는 데 O(logN)의 시간이 소요됩니다.
  • 따라서 정렬과 탐색의 총 시간복잡도는 O(NlogN) + O(logN)입니다.
  • 탐색을 여러 번 진행하는 경우가 아니라면, 이진탐색보다 순차탐색이 유리할 수 있습니다.

 

코드

function binary_search(arr[], target)
  set left = 0
  set right = arr.size - 1
  while left <= right
    set mid = (left + right) / 2
    if arr[mid] == target
      return mid

    if arr[mid] > target
      right = mid - 1
    else
      left = mid + 1
      
  return -1

---

2. Lower bound, Upper bound

찾는 값 target이 배열에 여러 개 있다면, 이진탐색을 돌렸을 때 어떤 위치가 나오게 될지는 아무도 모릅니다. 이때 lower bound와 upper bound를 활용하면, 특정 값이 존재하는 구간을 알 수 있습니다. [lower bound, upper bound)

Lower bound란?

원하는 값 target 이상이 처음으로 나오는 위치를 의미합니다. 이는 바꿔말해 target보다 같거나 큰 원소의 위치들 중 가장 작은 값을 의미합니다.

function lower_bound(arr, target)
  set left = 0                         // 첫 번째 원소의 위치로 설정합니다.
  set right = arr.size - 1             // 마지막 원소의 위치로 설정합니다.
  set min_idx = arr.size               // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
  while left <= right                  // [left, right]가 유효한 구간이면 계속 수행합니다.
    set mid = (left + right) / 2       // 가운데 위치를 선택합니다.
    if arr[mid] >= target              // 만약에 선택한 원소가 target보다 같거나 크다면 
      right = mid - 1                  // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에, right를 바꿔줍니다.
      min_idx = min(min_idx, mid)      // 같거나 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
    else
      left = mid + 1                   // 작은 경우라면 left를 바꿔줍니다.

  return min_idx                       // 조건을 만족하는 최소 index 값을 반환합니다.

 

Upper bound란?

원하는 값 target 초과인 값이 처음으로 나오는 위치를 의미합니다. 이는 바꿔말해 target보다 같거나 큰 원소의 위치들 중 가장 작은 값을 의미합니다.

function upper_bound(arr, target)
  set left = 0                         // 첫 번째 원소의 위치로 설정합니다.
  set right = arr.size - 1             // 마지막 원소의 위치로 설정합니다.
  set min_idx = arr.size               // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
  while left <= right                  // [left, right]가 유효한 구간이면 계속 수행합니다.
    set mid = (left + right) / 2       // 가운데 위치를 선택합니다.
    if arr[mid] > target               // 만약에 선택한 원소가 target보다 크다면 
      right = mid - 1                  // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에, right를 바꿔줍니다.
      min_idx = min(min_idx, mid)      // 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
    else
      left = mid + 1                   // 같거나 작은 경우라면 left를 바꿔줍니다.

  return min_idx                       // 조건을 만족하는 최소 index 값을 반환합니다.

 

Lower/Upper bound를 활용한 target의 개수

• Lower Bound == UpperBound인 경우
  • 배열 내에 target은 존재하지 않습니다.
• Lower Bound ≠ Upper Bound인 경우
  • 배열 내에 target은 (Upper Bound - Lower Bound)개 존재합니다.

 

Custom bound

Upper bound를 조금 변형하여, 원하는 값 target 이하의 값이 마지막으로 나오는 위치도 알 수 있습니다. 이는 바꿔말해 target보다 같거나 작은 원소의 위치들 중 가장 큰 값을 의미합니다.

function custom_bound(arr, target)
  set left = 0                         // 첫 번째 원소의 위치로 설정합니다.
  set right = arr.size - 1             // 마지막 원소의 위치로 설정합니다.
  set max_idx = -1                     // 최대이므로, 답이 될 수 있는 값보다 더 작은 값으로 설정합니다.
  while left <= right                  // [left, right]가 유효한 구간이면 계속 수행합니다.
    set mid = (left + right) / 2       // 가운데 위치를 선택합니다.
    if arr[mid] <= target              // 만약에 선택한 원소가 target보다 같거나 작다면 
      left = mid + 1                   // 오른쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에, left를 바꿔줍니다.
      max_idx = max(max_idx, mid)      // 같거나 작은 값들의 위치 중 최댓값을 계속 갱신해줍니다.
    else
      right = mid - 1                  // 값이 더 큰 경우라면 right를 바꿔줍니다.

  return max_idx                       // 조건을 만족하는 최대 index 값을 반환합니다.