1208 이진 탐색 : upper_bound 및 lower_bound 찾기

 

조건 : 배열이 오름차순되어 있다.

정의 : 

lower bound target이 시작되는 첫번째 index.

upper bound target이 종료되는 index의 +1.

ex)

//1, [2], 2, 2, [3], 4,4,4,4,4,4,4,4,4,4,4,4

 

upper_bound - lower_bound = target의 개수.

 

public static void main(String[] args) throws IOException {

		int[] arr1 = { 1, 1, 1,1,1,1,1,1,1,1,1,1, 2, 2, 2, 3, 4 };
		int[] arr2 = { 1, 2, 2, 2, 3, 4,4,4,4,4,4,4,4,4,4,4,4 };
		
		//1, 1, 1,1,1,1,1,1,1,1,1,1, [2], 2, 2, [3], 4
		System.out.println("upper_bound : " + upper_bound(arr1, 2, 0));
		System.out.println("lower_bound : " + lower_bound(arr1, 2, 0));
		
		 //1, [2], 2, 2, [3], 4,4,4,4,4,4,4,4,4,4,4,4
		System.out.println("upper_bound : " + upper_bound(arr2, 2, 0));
		System.out.println("lower_bound : " + lower_bound(arr2, 2, 0));

	}

	private static int lower_bound(int[] a, int t, int s) {
		int rt = a.length;
		int lt = s;

		while (lt < rt) {
			int mid = (rt + lt) / 2;

			if (t <= a[mid]) {
				rt = mid;
			} else if (t > a[mid]) {
				lt = mid + 1;
			}
		}

		return rt;
	}

	private static int upper_bound(int[] a, int t, int s) {
		int rt = a.length;
		int lt = s;

		while (lt < rt) {
			int mid = (rt + lt) / 2;
			if (t >= a[mid]) {
				lt = mid + 1;
			} else if (t < a[mid]) {
				rt = mid;
			}
		}
		System.out.printf("l : %d r : %d\n", lt, rt);
		return rt;
	}
    
    
upper_bound : 15
lower_bound : 12

upper_bound : 4
lower_bound : 1