A
Size: a a a
A
D
D
V🇺
p(i)
и отрезок поиска [L, R]
.<= x
и не выполняется для чисел > x
.p(L-1) = true
и p(R+1) = false
.l=L-1
и r=R+1
и будем поддерживать инвариант p(l)=true
и p(r)=false
внутри цикла.int binarySearch(int L, int R, function<bool(int)> p) {
int l = L-1, r = R+1;
while (l + 1 < r) { // итерируемся пока l и r не будут соседними числами
int mid = (l + r) / 2; // если l и r не соседи то mid != l, mid != r
if (p(mid)) {
l = mid;
} else {
r = mid;
}
}
return l; // для i <= l p(i) == true, для i > l (i >= r) p(i) == false
}
p(i) = a[i] <= k; L=0; R=n.
На выходе получим максимальный индекс x
такой, что a[x] <= k
. Если k
есть в массиве то a[x] == k
.p(i) = a[i] < a[i+1]; L=0; R=len(a)-1.
x
такой, что a[x] < a[x+1] > a[x+2]
.A
A
V🇺
V🇺
V🇺
V🇺
A
V🇺
A
V🇺
A
GM
A
A