Wie sollte ich die binäre Suche verwenden, um zu ermitteln, ob in einem sortierten Array ein Abstand zwischen benachbarten Zahlen größer als N ist? Beispielsweise:
Input: 2 5 8 11 16
Distance: 4
Also sollten wir die Antwort bekommen, dass es solch eine Distanz zwischen Nachbarn gibt. (zwischen 11 und 16)
EDIT: Lass mich klarer werden, warum ich das mit binärer Suche machen möchte.
Angenommen, das INPUT-Array wird unsortiert. Ex:
Input: 11 8 2 16 5
Dann sollten Sie das Array sortieren, um zu sehen, welche die Nachbarn sind. Also, nachdem wir eine sortierte Liste haben, ist es nicht der beste Weg, die Entfernung mit einer Mutation der binären Suche zu finden?
Antworten:
0 für die Antwort № 1Sie können die binäre Suche im Worst-Case-Szenario nicht verwenden, wenn alle Zahlen gleichmäßig verteilt sind N.
Die Idee einer binären Suche und anderer Divide-and-Conquer-Algorithmen besteht darin, dass Sie bei jedem Schritt etwa die Hälfte des verbleibenden Bereichs eliminieren. Wenn alle Elemente im Abstand angeordnet sind N, jeder Bereich von drei oder mehr aufeinander folgenden Elementen könnte möglicherweise ein Paar von Nachbarn mit der Entfernung von > N, so dass Sie keinen der beiden betrachteten Teilbereiche eliminieren können. Sie werden schließlich jedes einzelne Paar aufeinander folgender Gegenstände untersuchen, die Sie kosten O(NumItems).
Das heißt, Sie können einen allgemeinen Fall wahrscheinlich erheblich besser optimieren als O(NumItems) wegen möglicher Beschneidungsmöglichkeiten.
0 für die Antwort № 2
Du (gut, ich) würde nicht: Die binäre Suche erfordert eine sortierte Liste, und Sie werden mehr Zeit damit verbringen, diese Liste (von Paaren benachbarter Elemente, geordnet nach ihrer Entfernung) zu sortieren, als Sie die Liste nur scannen würden.