[코드트리 조별과제] lower, upper bound

 

이진탐색 중 Lower Bound와 Upper Bound가 있다. 정렬된 배열에서 같은 값이 여러개인 경우 해당 알고리즘을 사용한다.

 

- Lower: 같은 값들 중 가장 왼쪽에 있는 인덱스 리턴

- Upper: 같은 값들 중 가장 오른쪽에 있는 값 한칸 옆에 있는 값 리턴 -> 1,2,3,3,3,4배열에서  target = 3인경우 4가 있는 위치 리턴

 

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 값을 반환합니다.

 

lower의 경우 target이 arr[mid]보다 같거나 크다면 min_idx에 최솟값을 넣는다. 같거나 클 때 min을 초기화하는 이유는 같은 값을 가진 값 중 가장 작은 값을 찾아야하기 때문이다.

 

즉 값을 찾았을 때 값이 초기화 돼야한다.이와 반대로 Upper의 경우 같은 값을 찾는게 아니라 타겟 값 +1인 값을 찾기 때문에 같거나 큰 값이 아닌 큰 값만 찾는다.

 

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 값을 반환합니다.