ある条件下の最大の index を二分探索で取得

実現したいこと

ある条件下の最大の index を二分探索で取得

ある数以下

upperBound で実現できる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int[] a = {18, 37, 75, 80, 80, 93, 107, 144, 163, 196};

            int num = 40;
            int idx = upperBound(a, num);
            out.printf("index = %d (a[%d] = %d)\n", idx - 1,idx - 1 , a[idx - 1]);

            num = 80;
            idx = upperBound(a, num);
            out.printf("index = %d (a[%d] = %d)\n", idx - 1,idx - 1 , a[idx - 1]);

        }

出力結果

index = 1 (a[1] = 37)
index = 4 (a[4] = 80)

ある数未満

lowerBound で実現できる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int[] a = {18, 37, 75, 80, 80, 93, 107, 144, 163, 196};

            int num = 40;
            idx = lowerBound(a, num);
            out.printf("index = %d (a[%d] = %d)\n", idx - 1,idx - 1 , a[idx - 1]);

            num = 80;
            idx = lowerBound(a, num);
            out.printf("index = %d (a[%d] = %d)\n", idx - 1,idx - 1 , a[idx - 1]);

        }

出力結果

index = 1 (a[1] = 37)
index = 2 (a[2] = 75)