이진탐색(lower bound, upper bound)

1. lower bound & upper bound algorithm

2. lower bound algorithm

int[] lower bound = {1,2,2,3,3,4,5,6,7} 이 주어질때 이진탐색은 정확히 같은 값이 있는곳을 찾는거지만 lower bound는 주어진 값보다 같거나 큰 값이 처음으로 나오는걸 리턴해야 하는데 만약 lower_bound(8) 면 주어진 배열크기 만큼 리턴되어야 하기 때문에 high = array.length -1 이 아니고 high = array.length로 지정 해야 한다.

3. upper bound algorithm

int[] lower bound = {1,2,2,3,3,4,5,6,7} 이 주어질때 이진탐색은 정확히 같은 값이 있는곳을 찾는거지만 lower bound는 주어진 값보다 같거나 큰 값이 처음으로 나오는걸 리턴해야 하는데 만약 lower_bound(8) 면 주어진 배열크기 만큼 리턴되어야 하기 때문에 high = array.length -1 이 아니고 high = array.length로 지정 해야 한다.

4. 코드로 이해

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);	// 이분 탐색을 하기 위해서 정렬.
        
        int target = in.nextInt();
        System.out.println(upperBound(arr, target));
    }
    private static int lowerBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (target <= arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
    private static int upperBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            System.out.println(low+","+high);
            int mid = (low + high) / 2;
            if (target < arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
}

출력 결과

9
1 2 3 4 4 4 5 5 7
4
0,9
5,9
5,7
5,6
6

Process finished with exit code 0

5. reference

http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html