Upper Bound, Lower Bound

public class LowerUpper {
    public static int upperBound(int arr[],int front, int rear, int key) {
        int mid;
        while(front<rear) {
            mid = (front + rear)/2;
            if(arr[mid] <= key) front = mid +1;
            else rear = mid;
        }
        return rear;
    }
    
    public static int lowerBound(int arr[],int front,int rear, int key) {
        int mid;
        while(front<rear) {
            mid = (front + rear) /2;
            if(arr[mid] < key) front = mid +1;
            else rear = mid;
        }
        return rear;
    }
}
 

 

로워바운디드와 업퍼바운디드 key값을 기준으로 초과하는값이 처음나오는 것을 찾을때 upper

 

이상인것이 처음 나오는것을 찾을때는 lower를 사용한다.

 

front는 왼쪽 rear을 오른쪽을 생각하면 되는데  mid 값 을 기준으로 key 값이 오른쪽에잇냐 왼쪽에 잇냐가 중요하다.