이분탐색 / Upper Bound / Lower Bound

이분탐색

public static int[] arr = {1, 2, 3, 3, 3, 4, 5, 6};
public static int binary_search(int[] arr, int target){
	int left = 0, right = arr.length - 1;

	while (left <= right) {
    		int mid = (left + right) / 2;
    		if (arr[mid] == target) {
        		return mid;
    		else if (arr[mid] > target) {
				right = mid - 1;
        	}
        	else if (arr[mid] < target) {
        		left = mid + 1;
        	}
    	}
	return -1;
}

• 이분 탐색을 위해서는 리스트 정렬이 필수
• 중간 위치의 값과 찾으려는 값을 반복적으로 비교하여 mid값이 target인 경우의 인덱스 반환
  • 반복문 / 재귀함수 사용 가능
• Java에 이진탐색을 제공하는 메소드 존재

List<Integer> list;

Collections.sort(list);
Collections.binarySearch(list, target);

int[] arr;

Arrays.sort(arr);
Arrays.binarySearch(arr, target);

 

일반적인 이분탐색은 target과 일치하는 중복된 값이 있다면 가장 먼저 발견되는 인덱스가 반환됨 !

≫ 특정 값(target)보다 처음으로 큰 값의 위치를 알고 싶다면 ?   Upper Bound

≫ 특정 값(target)의 시작 위치를 알고 싶다면 ?   Lower Bound

≫ Upper Bound, Lower Bound 모두 이분탐색 기반으로 함

 

 

Upper Bound

public static int[] arr = {1, 2, 3, 3, 3, 4, 5, 6};
public static int upper_bound(int[] arr, int target){
	int left = 0, right = arr.length - 1;
    
    	while (left < right) {
    		int mid = (left + right) / 2;
        	if (arr[mid] <= target) {
        		left = mid + 1;
        	}
        	else if (arr[mid] > target) {
        		right = mid;
        	}
    	}
    	return left;
}

• target 보다 큰 값이 처음 나오는 위치 찾기
• arr[mid] <= target : mid는 답이 될 수 없음 ≫ left = mid + 1 ≫ mid를 포함시키지 않고 범위를 좁힘
• arr[mid] > target : mid는 답이 될 수 있는 후보값 ≫ right = mid ≫ mid 포함하면서 범위를 좁힘
• 종료 조건에 도달하면 left와 right는 결국 같은 값을 가리킴 ≫ return left or return right

 

 

Lower Bound

public static int[] arr = {1, 2, 3, 3, 3, 4, 5, 6};
public static int lower_bound(int[] arr, int target) {
	int left = 0, right = arr.length - 1; 
    
    	while (left < right) {
    		int mid = (left + right) / 2;
        	if (arr[mid] >= target) {
        		right = mid;
        	}
        	else if (arr[mid] < target) {
        		left = mid + 1;
        	}
    	}
    	return left;
}

• target이 처음 등장하는 위치 찾기
• arr[mid] >= target : mid는 답이 될 수 있는 후보값 ≫ right = mid ≫ mid 포함하면서 범위를 좁힘
• arr[mid] < target : mid는 답이 될 수 없음 ≫ left = mid + 1 ≫ mid를 포함시키지 않고 범위를 좁힘
• left는 결국 target보다 크거나 같은 첫 번째 값을 가리키게 됨 ≫ return left
• 하지만 종료 조건에 도달하면 left와 right는 결국 같은 값을 가리킴 ≫ return right도 가능은 함