[Algorithm] Lower Bound & Upper Bound

Lower Bound & Upper Bound

하한선 알고리즘, 배열에서 특정한 값을 찾는 이 알고리즘은 이분 탐색(Binary Search)을 응용한 알고리즘으로, 정렬되어있는 배열에서 target이상의 값이 처음 나오는 위치를 찾는 알고리즘 이다.
반대되는 개념으로 Upper Bound(상한선)이 있으며, 이는 target이하의 값 중 가장 큰 값이 나오는 위치를 찾는다.

이진 탐색(Binary Search)류의 알고리즘은 target값이 나오지 않았을 때, 나오지 않을 것이라 판단되는 범위를 과감히 제외하고 탐색을 수행하기 때문에, 이진탐색 계열의 알고리즘을 수행할 때는 정렬이 필수로 되어있어야 한다.

Lower Bound

// target 이상의 값 중 가장 작은 값의 위치
public int lower_Bound(int[] arr, int target){
	int left = 0, right = arr.length;
    
	while(left < right){
		int mid = (left + right) / 2;
		if(arr[mid] >= target){
			right = mid;
		}else{
			left = mid + 1;
		}
	}
	return right;
}

Upper Bound

// target 이하의 값 중 가장 큰 값의 위치
public int upper_Bound(int[] arr, int target) {
	int left = 0, right = arr.length;
    
	while(left < right) {
		int mid = (left + right) / 2;
		if(arr[mid] <= target){
			left = mid + 1;
		}else{
			right = mid;
		}
	}
    
	return left;
}

Binary Search

// target의 위치 or target이 들어갈 수 있는 위치
public int binary_Search(int[] arr, int target){
	int left = 0, right = arr.legnth;
    
	while(left <= right){
    	int mid = (left + right) / 2;
        if( arr[mid] == target){
        	// target을 찾은경우.
              // 찾은 위치인 mid의 값을 리턴
              retun mid;
        }else if (arr[mid] < target){
        	left = mid + 1;
        }else{
        	right = mid - 1;
        }
	}
    // 전체를 탐색해도 나오지 않았다면, target값이 들어갈 수 있는 위치를 리턴
    return right;
}