이진탐색 - Lower bound, Upper bound

Target으로 찾는 값이 한 배열 안에 여러 개 존재할 때, target 값 이상의 값이 최초로 나오는 위치를 Lower Bound라고 한다.
Target을 초과하는 값 중, 가장 인접한 위치를 Upper Bound라고 한다.

Target보다 같거나 작은 숫자들 중, target 값이 마지막으로 나오는 위치를 Custom Bound라고 한다.

 

Lower Bound

public static int lowerBound(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	int minIdx = arr.length;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (arr[mid] >= target) {
			right = mid - 1;
			minIdx = Math.min(mid, minIdx);
		} else {
			left = mid + 1;
		}
	}
	return minIdx;
}

Upper Bound

public static int upperBound(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	int minIdx = arr.length;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (arr[mid] > target) {
			right = mid - 1;
			minIdx = Math.min(mid, minIdx);
		} else {
			left = mid + 1;
		}
	}
	return minIdx;
}

Custom Bound

public static int customBound(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	int maxIdx = -1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] <= target) {
			left = mid + 1;
			maxIdx = Math.max(maxIdx, mid);
		} else {
			right = mid - 1;
		}
	}
	return maxIdx;
}

 

특징

• Upper Bound - Lower Bound == 배열 내 존재하는 같은 수의 개수
• Upper Bound == Lower Bound => 배열 내에 Target 값이 존재하지 않는다.