Lower / Upper Bound

Binary Search (이분 탐색) 가 '원하는 값 x를 찾는 과정' 이라면, Lower Bound는 '원하는 값 x 이상이 처음 나오는 위치를 찾는 과정' 입니다. 마찬가지로 Upper Bound는 '원하는 값 x를 초과한 값이 처음 나오는 위치를 찾는 과정' 입니다.

 

따라서 Lower Bound와 Upper Bound를 이해하기 전에 Binary Search (이분 탐색) 에 대해 먼저 이해하고 오셔야 합니다❗️❗️

 

 

 

Lower Bound 의 계산 과정은 이분 탐색과 다를 바가 없습니다.

1. 탐색할 리스트는 정렬되어 있어야 한다.

2. start와 end, mid 변수로 이분탐색을 시작한다.

3. mid의 값이 number보다 작을 때 start를 mid+1로 설정한다.

4. mid의 값이 number보다 크거나 같을 때 end를 mid로 설정한다. (이분탐색에서는 mid-1)

👉 number 이상인 값이 처음 나오는 위치를 구하는 것이므로, mid가 Lower Bound가 될 수도 있기 때문

5. 2번부터 다시 반복

6. start == end가 될 때의 값이 Lower Bound가 된다.

 

이를 Swift로 다루면 아래와 같습니다.

list.sort() // 1.

var start: Int = 0 // 2.
var end: Int = list.count - 1
while start < end { // 5. 6.
    let mid: Int = (start+end)/2
    if list[mid] < number { // 3.
        start = mid+1
        continue
    }
    end = mid // 4.
}

// lowerBoundIndex: start

 

 

Upper Bound 도 Lower Bound와 거의 같습니다.

다만, 위의 Lower Bound 코드에서 크거나 같을 때 end = mid를 해주던 것을 클 때에만 end = mid를 해주는 것으로 수정해주면 됩니다.

list.sort() // 1.

var start: Int = 0 // 2.
var end: Int = list.count - 1
while start < end { // 5. 6.
    let mid: Int = (start+end)/2
    if list[mid] <= number { // 3.
        start = mid+1
        continue
    }
    end = mid // 4.
}

// upperBoundIndex: start