[Algorithm] LowerBound & UpperBound

다른 사람의 풀이를 확인하다가 몰랐던 새로운 알고리즘 발견했다. 

Lower Bound는 찾고자 하는 값 이상이 처음 나오는 인덱스를 찾는 것이다. 

Upper Bound는 찾고자 하는 값보다 큰 (초과) 값이 처음 나오는 인덱스를 찾는 것이다. 

두 알고리즘 모두 이분탐색을 활용한다. 

 

func lowerBound(arr: [Int], start: Int, end: Int, target: Int) -> Int {
    var start = start
    var end = end
    
    while start < end {
        let mid = (start + end) / 2
        // target 값보다 작을 때 start를 움직여 target보다 크거나 같은 첫번째 값의 인덱스를 찾는다.
        if arr[mid] < target {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return end
}

func upperBound(arr: [Int], start: Int, end: Int, target: Int) -> Int {
    var start = start
    var end = end
    
    while start < end {
        let mid = (start + end) / 2
        // target 값보다 작거나 같을 때 start를 움직여 target보다 큰 첫번째 값의 인덱스를 찾는다.
        if arr[mid] <= target {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return end
}


var nums = [1,2,3,4,6,7]
var target = 2

print(lowerBounds(arr: nums, start: 0, end: nums.count-1, target: target)) // 1 
print(upperBounds(arr: nums, start: 0, end: nums.count-1, target: target)) // 2

코드에서는 등호 하나의 차이이다.