Lower / Upper Bound : 하한 / 상한 알고리즘

Lower Bound : 찾는 값과 같거나 큰 값이 처음으로 나타나는 위치 (이상)

Upper Bound : 찾는 값 보다 큰 값이 처음으로 나오는 위치 (초과)

[1, 2, 5, 7, 8, 9, 11, 11, 11, 14] 인 배열에서 11의 Lower Bound와 Upper Bound의 과정은 아래와 같다.

Lower Bound	Upper Bound

Lower Bound / Upper Bound 코드

public static int lowerBound(int[] arr, int value) {
    int s = 0, m, e = arr.length-1;
    while(s<e) {
        m = (s+e)/2;
        if(arr[m]<value) s = m+1;
        else e = m;
    }
    return e;
}
 
public static int upperBound(int[] arr, int value) {
    int s = 0, m, e = arr.length-1;
    while(s<e) {
        m = (s+e)/2;
        if(arr[m]<=value) s = m+1;
        else e = m;
    }
    return e;
}