Binary Search 이진탐색(2) Lower/Upper bound

이진탐색이 정확히 원하는 값을 찾는 거라면,

lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다.

이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다.

이진탐색이 궁금하다면? --> 여기로

 

코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다.

lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다.

upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다.

[1, 2, 2, 3, 3, 3, 4, 6] 
LowerBound(3) --> 3
UpperBound(3) --> 6

[1, 2, 2, 3, 3, 3, 4, 6] 
LowerBound(4) --> 6
UpperBound(4) --> 7

[1, 2, 2, 3, 3, 3, 4, 6] 
LowerBound(5) --> 7
UpperBound(5) --> 7

[1, 2, 2, 3, 3, 3, 4, 6] 
LowerBound(6) --> 7
UpperBound(6) --> 8

[1, 2, 2, 3, 3, 3, 4, 6] 
LowerBound(7) --> 8
UpperBound(7) --> 8

예시를 보니 이해가 되시죠?

bound로 찾을 때는 배열의 모든 수가 타겟보다 작다면 범위 밖을 리턴해줘야 합니다. 
따라서 high는 count-1이 아닌 count가 됩니다.

그리고 일반 이진탐색에서 미드를 찾은 경우에 바로 리턴해줬던 것과 달리
미드를 찾았을 때 (target == mid)
low/high 를 한 번 더 조절해서 위치를 찾는 것이 핵심입니다.

이제 코드를 살펴보겠습니다. 

Lower bound

func binarySearchLowerBounds(_ arr: [Int], _ target: Int) -> Int {
    var low = 0
    var high = arr.count
        
    while low < high {
        let mid = (low + high)/2
        if target <= arr[mid] {
	    // target == arr[mid]에는 high를 옮겨준다.
            high = mid
        } else {
            low = mid + 1
        }
    }
    
    return low
}

 

Upper bound 

func binarySearchUpperBounds(_ arr: [Int], _ target: Int) -> Int {
    var low = 0
    var high = arr.count
        
    while low < high {
        let mid = (low + high)/2
        if target < arr[mid] {
            high = mid
        } else {
       	    // target == arr[mid]에는 low를 옮겨준다.
            low = mid + 1
        }
    }
    return low
}

 

low == high 에 어떻게 처리해줄지만 차이를 두면 되기 때문에 이런식으로 합칠 수도 있겠네요

Bound

// default를 lower로 해준 경우
func binarySearchBounds(_ arr: [Int], _ target: Int, upper: Bool = false) -> Int {
    var low = 0
    var high = arr.count
    
    while low < high {
        let mid = (low + high)/2
        if target == arr[mid] {
            // target을 찾은 경우에 어떻게 처리해줄지가 관건!
            upper ? (low = mid+1) : (high = mid)
        } else if target < arr[mid] {
            high = mid
        } else {
            low = mid + 1
        }
    }
    
    return low
}

 

오늘도 화이팅입니다.

감사합니다 :)