LowerBound & UpperBound

최근에는 이분 탐색을 많이 쓰지 않았다가 얼마 전 카카오 문제 중 순위 검색의 효율성을 해결하기 위해 다시 찾아봤다. 전에 C++ 로 알고리즘 짤 때는 algorithm 라이브러리에 lowerbound 함수가 있어서 그걸 사용했었는데 이젠 필요하면 직접 구현해야하니까 이 참에 개념을 확실히 정리해두는게 좋을 것 같다는 생각이 들었다. 이런게 또 정확히 기억 안나면 사소한 부분 때문에 헷갈린다,,

 

참고. Lower bound basics

 

LowerBound

• 찾고자 하는 값 이상이 처음 나오는 위치(인덱스)를 찾는 알고리즘이다.

func lowerBound(_ sortedArr: [Int], _ target: Int) -> Int {

    var start = 0
    var end = scores.count

    while start < end {
        let mid = (start + end) / 2
        if sortedArr[mid] < target {
            start =  mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}

찾고자 하는 값 이상이라는 말은 같거나 큰 값을 찾는 것인데

• mid 의 값이 찾으려는 값보다 작다면

→ 적어도 mid 의 위치는 아니라는 거니까

→ s 에 mid 의 다음 위치를 넣어야 하는 것이다.

 

• 또한 mid 의 값이 찾으려는 값보다 크거나 같다면

→ 찾으려는 값이 그 범위 내에 있다는 뜻이니까

(현재 그 위치가 찾으려는 그 값일 수 도 있으니까)

→ e 에 mid 의 위치를 넣는 것이다.

 

UpperBound 

• 찾고자 하는 값보다 큰 (초과) 값이 처음 나오는 위치(인덱스)를 찾는 알고리즘이다.

func upperBound(_ sortedArr: [Int], _ target: Int) -> Int {

    var start = 0
    var end = scores.count

    while start < end {
        let mid = (start + end) / 2
        if sortedArr[mid] <= target {
            start =  mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}

찾고자 하는 값 보다 큰 값이라는 말은 같은 값은 허용하지 않겠다는 말인데

• mid 의 값이 찾으려는 값보다 작거나 같다면

→ 적어도 mid 의 위치는 아니라는 거니까

→ s 에 mid 의 다음 위치를 넣어야 하는 것이다.

 

• 또한 mid 의 값이 찾으려는 값보다 크다면

→ 찾으려는 값이 그 범위 내에 있다는 뜻이니까

(현재 그 위치가 찾으려는 그 값일 수 도 있으니까)

→ e 에 mid 의 위치를 넣는 것이다.

 

우선 두 개념의 차이는 찾고자 하는 값과 같은 값을 포함하는지의 여부이다. 따라서 알고리즘은 거의 동일하지만 target 값과 mid 위치의 값을 비교할 때 같은지의 여부 가 포함(lowerbound)되거나 포함되지 않는다(upperbound)는 점이 다르다.

 

💡 e 의 초기 값이 배열의 마지막 인덱스가 아니라 배열의 크기(마지막 인덱스 + 1)여야 하는 이유

만약 찾고자 하는 위치가 배열 범위 내에 없다면, 즉 위 그림에서 8 이상(혹은 보다 큰 값)의 위치를 찾는다면

결과적으로 배열 내에서는 조건을 만족하는 위치가 없기 때문에 마지막 인덱스 + 1을 반환해야 할 것이다.

(이것은 이 배열 내에는 만족하는 위치가 없다는 사실을 의미하게 되는 것이다.)

 

하지만 만일 e 의 초기 값이 배열의 마지막 인덱스라면,

8 이상(혹은 보다 큰 값)의 위치를 찾지 못하더라도 결국 s 와 e 의 위치가 같아지면서 e (마지막 인덱스 위치)를 반환하게 될 것이다. (while 문의 조건이 거짓이 되므로 이대로 탐색은 종료가 된다)

 

하지만 이것은 올바른 위치가 아니므로 (배열 내에 만족하는 위치가 없음에도 마치 있는 것처럼 거짓을 말하게 된다) e의 초기 값은 배열의 마지막 인덱스보다 1이 큰 값으로 시작해야 한다.