이진탐색 LowerBound, UpperBound 이해하기 - Swift

정의

• 이진 탐색 : 정렬 되어 있는 배열에서 특정 요소를 찾을 때 사용할 수 있는 알고리즘
• LowerBound :  정렬 되어 있는 배열에서 그 요소가 시작되는 첫번째 인덱스 (중복값 들어있을 때 사용 가능)
• UpperBound : 정렬 되어 있는 배열에서 그 요소가 끝나는 다음 인덱스 (중복값 들어있을 때 사용 가능)

정의는 이러한데 읽고 코드를 봐도 머릿속에서 그림이 안그려지더라구요. 그래서 그림을 그려보면서 이해해보겠습니다.

 

문제 상황

[1, 2, 3, 3, 4, 5] 에서 3을 찾을 때 

LowerBound = 처음으로 3이 나오는 인덱스 

UpperBound = 마지막 3의 다음 인덱스 

 

LowerBound 

코드

func lowerBound(_ element: Int, in arr: [Int]) -> Int {
    var start = 0
    var end = arr.count
    
    while start < end {
        let mid = (start+end) / 2
        let val = arr[mid]
        
        if val < element {
            start = mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}

 

UpperBound

코드

func upperBound(_ element: Int, in arr: [Int]) -> Int {
    var start = 0
    var end = arr.count
    
    while start < end {
        let mid = (start+end) / 2
        let val = arr[mid]
        
        if val <= element {
            start = mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}