upper bound, lower bound 이분탐색

일반적인 이분탐색은 

비내림차순, 비오름차순 으로 정렬된 상태가 아니고,

아래와 같이 공통된 값 없이 하나씩만 존재하는 경우이다. 

이분탐색에 필요한 left,  right값을 아래와 같이 정의하고,

left = -1 (배열을 벗어난 가장 왼쪽에 가까운 값)과

right = n (배열을 벗어난 가장 오른쪽에 가까운 값)

 

 

while문은 left +1 = right 가 되는 시점에 멈추게 되고,

 

• left는 항상 target보다 작은 값 중 최대 값을 가리킴
• right는 항상 target 이상인 값 중 최소 값을 가리킴

이므로, 최종적인 right값을 반환한다.

 

int left = -1;
int right = n;
binarysearch(left, right);

public static int binarysearch(int left, int right){
	while(left+1<right){
    	int mid = (left+right) / 2;
        if (arr[mid] < target){
        	left = mid;
        }else{
        	right = mid;
        }
    }
    return right;
}

 

그럼 이제 upper bound, lower bound에 대해서 알아보자.

upper bound

upper bound는 중복된 값이 섞여있을 때 정렬한 상태에서

찾고자 하는 값보다 처음으로 큰 값이 나오는 위치이다. 그림으로 살펴보면 이해가 더 잘된다.

해당 부분에서 오른쪽 초록색 화살표가 가리키는 부분

upper bound를 구하기 위해서는 일반적인 이분탐색 코드를 어떻게 변경해야할까 ? 

우선 배열a와 target(이하 t) 를 7이라 하고 아래 예시로 보자.

1)

left = -1, right = 8

중간 위치를 계산하면 mid = (-1 + 8 ) / 2 = 3이다.

a[3]의 값은 7이므로, 탐색 구간을 [4,8]로 바꾼다.

upper bound는 t를 초과하는 값중 탐색해야하므로, 3을 제외하여 탐색 구간을 정한다.

 

2) 

left = 4, right = 8

중간 위치를 계산하면 mid = (4 + 8 ) / 2 = 6이다.

a[6]의 값은 11 이므로, 탐색 구간을 [4,6]으로 바꾼다.

 

3)

left = 4, right = 6

중간 위치를 계산하면 mid = (4+6)/2 = 5이다.

a[5] 의 값은 7이므로, 1)에서와 같이 5를 제외하여 탐색 구간을 [6,6]으로 바꾼다.

 

4) 

[6,6]은 탐색하지 않아도 되므로, 6 위치가 찾고자 하는 upper bound임을 알 수 있다.

 

해당 부분을 코드로 짜면 아래와 같다.

 

• left는 항상 target 이하의 값을 가리킴.
• right는 항상 target보다 큰 값을 가리킴.

 

 

int left = -1;
int right = n;
binarysearch(left, right);

public static int binarysearch(int left, int right){
	while(left+1<right){
    	int mid = (left+right) / 2;
        if (arr[mid] <= target){
        	left = mid+1; //mid제외
        }else{ //arr[mid] > target
        	right = mid; //mid 포함
        }
    }
    return right;
}

 

lower bound

lower bound는 정렬되어있는 배열에서 k값 이상이 처음 발견되는 위치를 말한다.

int left = -1;
int right = n;
binarysearch(left, right);

public static int binarysearch(int left, int right){
	while(left + 1 < right){
    	int mid = (left + right) / 2;
        if (arr[mid] < target){//target보다 작으면 제외
        	left = mid;
        } else {
        	right = mid;
        }
    }
    return right; //target 이상인 첫 번째 위치
}

백준 10816

lower bound, upper bound를 구현하는 문제이다.

처음에, arr[mid] (부등호) target 이 부분이 어려웠는데, 위와 같이 뜯어보니 이해가 된다. 

while문 조건은 left = right가 일치되는 경우 끝나는 식으로 작성했다.

package 알고리즘_코딩테스트.dayone.mar28;

import java.io.*;
import java.util.*;

public class BOJ_10816 {
/*
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

3 0 0 1 2 0 0 2
 */
    static int n, m;
    static int[] arr, srr;
    static BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));


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

        input();

        solve();
    }
    private static void solve() {
        StringBuilder sb = new StringBuilder();
        Arrays.sort(arr);

        for(int i = 0 ; i < m; i++){
           int target = srr[i];
          int lower_bound = lower(-1, n, target);
          int upper_bound = upper(-1, n, target);
          int size = upper_bound- lower_bound;
          sb.append(size+" ");
        }

        System.out.println(sb);

    }
    /*
    0 1 2 3  4  5   6   7  8 9
    6 3 2 10 10 10 -10 -10 7 3
    10 찾기

    left = -1, right = 10, mid = 4
    right = 4, left = -1

    left = -1, right = 4, mid = 1
    left = 2, right = 4

    left = 2, right = 4, mid = 3
    right = 3, left = 2

    left = 2, right = 3, mid = 2
    left = 3, right = 3
     */

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

        return right;
    }
    /*
    0 1 2 3  4  5   6   7  8 9
    6 3 2 10 10 10 -10 -10 7 3
    10 찾기

    left = -1, right = 10, mid = 4
    left = 4, right = 10

    left = 4, right = 10, mid = 7
    left = -1, right = 3

    left = 2, right = 4, mid = 3
    right = 3, left = 2

    left = 2, right = 3, mid = 2
    left = 3, right = 3
     */

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

        return right;
    }

    private static void input() throws IOException{
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(bf.readLine());
        int i = 0;
        while(st.hasMoreTokens()){
            arr[i] = Integer.parseInt(st.nextToken());
            i++;
        }

        st = new StringTokenizer(bf.readLine());
        m = Integer.parseInt(st.nextToken());
        srr = new int[m];
        st = new StringTokenizer(bf.readLine());
        i = 0;

        while(st.hasMoreTokens()){
            srr[i] = Integer.parseInt(st.nextToken());
            i++;
        }


    }
}