Elegante Art und Weise, zwei aufeinanderfolgende Werte in einem sortierten Feld zu finden, die einen bestimmten Wert begrenzen?

Question

Ich habe ein Array von sortierten Ganzzahlen, und ich möchte die zwei aufeinanderfolgenden Indizes der Elemente, die einen bestimmten Wert binden, die ich in übergeben zu erhalten. Zur Veranschaulichung, weil es schwer in Worten zu beschreiben ist, nehmen wir an, ich habe ein Array (regulär null-indiziert):

1 3 4 5 7 9

Ich möchte die beiden Indizes ermitteln, die z. B. den Wert 6 begrenzen. In diesem Fall hat das Array die Werte 5 und 7 an aufeinanderfolgenden Positionen, die den gesuchten Wert begrenzen (5 <= 6 <= 7), und so würde ich den Index von 5 und den Index von 7 (3 bzw. 4) zurückgeben.

Ich habe dies derzeit in einer sehr Brute-Force-Mode implementiert, mit einer Menge von Sortierungen und Suchen im Array. Darüber hinaus habe ich das Gefühl, ich bin eine Menge von Eckfällen (vor allem mit Werten, die größer/kleiner als der größte/kleinste Wert im Array sind) fehlt.

Gibt es eine elegante Möglichkeit, dies zu tun? Auf welche Eckfälle sollte ich achten und wie kann ich damit umgehen bzw. sie überprüfen? Vielen Dank!

Answer 1

Man kann das Problem mit Hilfe der binären Suche lösen, um es in O(lg(n)) zu lösen, ohne so viele Grenzfälle zu berücksichtigen. Die Idee ist, die binäre Suche zu verwenden, um das niedrigste Element zu finden, das größer oder gleich dem zu begrenzenden Wert ist (nennen wir es x ).

pair<int, int> FindInterval(const vector<int>& v, int x) {
  int low = 0, high = (int)v.size();
  while (low < high) {
    const int mid = (low + high) / 2;
    if (v[mid] < x) low = mid + 1;
    else high = mid;
  }
  // This if is used to detect then a bound (a <= x <= x) is impossible but a
  // bound (x <= x <= can be found).
  if (low == 0 && low < (int)v.size() && v[low] == x) ++low;
  return make_pair(low - 1, low);
}

Beachten Sie, dass die Antwort lauten könnte (-1, 0) , was bedeutet, dass es keine untere Schranke für das Intervall gibt, könnte es sein (n - 1, n) , was bedeutet, dass es keine obere Grenze für das Intervall gibt (wobei n ist die Größe von v ). Es gibt auch zwei mögliche Antworten, wenn x ist in v und es kann mehrere Antworten geben, wenn x ist mehrfach in v weil die Grenzen die Extreme einschließen.

Schließlich können Sie die binäre Suche durch die std::lower_bound Funktion:

pair<int, int> FindInterval(const vector<int>& v, int x) {
  // This does the same as the previous hand-coded binary search.
  const int low = (int)(lower_bound(v.begin(), v.end(), x) - v.begin());

  // The rest of the code is the same...
}

Answer 2

Im Grunde genommen:

1. Sortieren Sie das Array ( einmal );
2. Führen Sie eine Zweiteilungssuche durch, um das nächstgelegene Element zu finden;
3. Vergleichen Sie dieses Element mit dem Eingabewert;
   • Wenn sie niedriger ist, haben Sie die untere Grenze;
   • Wenn sie höher ist, haben Sie die höhere Grenze;
   • Wenn es derselbe ist, befinden sich die Grenzen neben dem Element.

Wenn Sie nun wiederholte Werte in dem Array haben können, ist der letzte Schritt etwas komplizierter. Möglicherweise müssen Sie mehrere Werte überspringen.

Letztendlich ist dies kaum mehr als eine Bisektionssuche auf einem sortierten Array, also O(log n) auf einem sortierten Array und O(n log n) auf einem unsortierten Array.

Answer 3

Binäre Suche nach dem gewünschten Wert (in diesem Fall 6).

Wenn er gefunden wird, werden der vorherige und der nächste Wert aus dem resultierenden Index übernommen.

Ist dies nicht der Fall, wird der endgültige Suchwert entweder kleiner sein als oder größer als Ihr Zielwert. Wenn er größer ist, liegen die Begrenzungswerte bei diesem und dem vorhergehenden Index. Andernfalls befinden sie sich bei diesem und dem nächsten Index.

Answer 4

Eine Möglichkeit, dies zu beschleunigen, wäre die Verwendung von binäre Suche . Dies wird die derzeitige Zeitkomplexität von O(n) a O(log n) .