Algorithmen und Datenstrukturen · Middle · Frage 13 von 75
Was liefert diese binäre Suche, wenn target nicht im Array steht?
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}- 1Den Index des Elements, das
targetdem Wert nach am nächsten ist - 2
-1, was bedeutet, dass der Wert nicht gefunden wurde - 3Den Index, an dem man
targetunter Erhalt der Ordnung einfügen könnte
Antwort zeigen
Richtige Antwort: Den Index, an dem man target unter Erhalt der Ordnung einfügen könnte
Erklärung
Das ist Lower Bound: der erste Index mit einem Wert >= target. Sind alle Werte kleiner, liefert es arr.length. Es ist die Grundlage vieler Varianten: Vorkommen zählen, Bereiche finden, in ein sortiertes Array einfügen.