ある条件下の最大の 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)