バイナリナビゲーション

2320 ワード
アルゴリズム#アルゴリズム# テキストリンク
1. lower bound & upper bound algorithm

2. lower bound algorithm

int[]下限={1,2,2,3,3,4,5,6,7}の場合、バイナリプローブは同じ値を持つ場所を正確に検索するが、下限は所定の値と等しいか、最初の値より大きい値を返さなければならない.下限(8)の場合、所定の配列サイズの値を返さなければならないため、high=arrayである.length-1はhigh=arrayではありません.lengthとして指定する必要があります.
3. upper bound algorithm

int[]下限={1,2,2,3,3,4,5,6,7}の場合、バイナリプローブは同じ値を持つ場所を正確に検索するが、下限は所定の値と等しいか、最初の値より大きい値を返さなければならない.下限(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
register_shutdown_function vs __destruct
インタフェースタイプ参照Objectクラスを呼び出す方法