Upper Bound와 Lower Bound

• 정렬되어 있는 리스트에서 특정 위치를 찾기 위해 사용하는 알고리즘
• Binary Search를 약간 변형한 형태
  • Upper Bound: 특정 숫자보다 큰 숫자들 중 가장 작은 숫자의 인덱스 반환
  • Lower Bound: 특정 숫자보다 같거나 큰 숫자들 중 가장 작은 숫자의 인덱스 반환

 

int upperBound(List<Integer> list, int target) {
	if (list == null || list.size() == 0)
		return -1;

	int l = 0, r = list.size() - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (list.get(mid) <= target)
			l = mid + 1;
		else
			r = mid;
	}

	return list.get(l) > target ? l : -1;
}

 

int lowerBound(List<Integer> list, int target) {
	if (list == null || list.size() == 0)
		return -1;

	int l = 0, r = list.size() - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (list.get(mid) < target)
			l = mid + 1;
		else
			r = mid;
	}

	return list.get(l) >= target ? l : -1;
}