Binäre Suche mit Array

[Lausemausiii]

Guten Abend,

ich habe einen Array (points) erstellt der aus zwei Elementen i und id besteht:
[[0, 61], [62, 100], [88, 101], [140, 102], [107, 103],...]

Meine Frage ist nun wie ich mit Hilfe der Binären Suche id=101 eingeben kann und dann mir i=88 angezeigt wird.
Für jede Hilfe wäre ich sehr dankbar!

Bislang habe ich diesen Code erstellt:

def binarySearch(points, id):
first = 0
last = len(points)-1
found = False

while (first<=last and not found):
mid = (first + last)//2
if points[mid] == id:
found = True
else:
if id < points [mid]:
last = mid - 1;
else:
first = mid +1;

print('Binäre Suche:', binarySearch(points, 101))

Funktioniert leider nicht....

[__deets__]

Bitte in Zukunft die code-Tags verwenden (im vollstaendigen Editor der </>-Knopf) damit man den Quelltext lesen kann - insbesondere die wichtigen Einrueckungen gehen so verloren.

Und dein Problem besteht hauptsaechlich darin, dass du mit points[mid] arbeitest. Das ist aber ja nicht wirklich der Wert, den du suchst, sondern das Tupel aus (i, id).

Du musst laso einmal zu Beginn der while-Schleife

Code: Alles auswählen

current_value, current_id = points[mid]

machen, und dann einfach mit current_id weiterarbeiten, statt points[mid]. Dann sollte das eigentlich ganz gut aussehen.

[Lausemausiii]

Vielen lieben Dank für die super schnelle Antwort!
Ich habe mich eben erst registriert, danke für die Tipps.
Leider kommt im Commando trotzdem immer "Binäre Suche: None"


points.sort (key=lambda id: id[1])

print(points)

#Binäre Suche:
def binarySearch(points, id):
first = 0
last = len(points)-1
found = False

while (first<=last and not found):
mid = (first + last)//2
current_value, current_id = points[mid]
if current_id == id:
found = True
else:
if id < current_id:
last = mid - 1;
else:
first = mid +1;

print('Binäre Suche:', binarySearch(points, 101))

[__deets__]

Bitte die Code-Tags verwenden.

Ich schaue mir den Code mal an.

[__deets__]

Achso. Du musst natuerlich dann auch den Wert current_value mit return zurueckgeben, den du gefunden hast. Wenn du einen gefunden hast. Und du kannst das dann auch direkt an der Stelle tun, wo du feststellst, dass du etwas gefunden hast. Und den ganzen "found"-Kram sparen. Und die Semikola hinter den Zeilen haben da nix verloren.

[Lausemausiii]

Wow ich habs *_* vielen lieben Dank!!!

Wie kann ich die Code-Tags verwenden dass es hier eingerückt erscheint?

[Sirius3]

Wie kann ich die Code-Tags verwenden dass es hier eingerückt erscheint?

Indem Du den passenden Knopf im Vollständigen Editor drückst </>.

Code: Alles auswählen

def binary_search(points, id):
    first = 0
    last = len(points) - 1
    while first <= last:
        mid = (first + last) // 2
        current_value, current_id = points[mid]
        if current_id == id:
            return current_value
        if id < current_id:
            last = mid - 1
        else:
            first = mid + 1
    raise KeyError(id)