Binäre Suche
In diesem Artikel erkläre ich in einem Video die binäre Suche und die Vorteile gegenüber der sequentiellen Suche. Ausserdem gibt es eine Beispielimplementierung.
Videoerklärung
Beispielimplementierung in Python
Diese Beispielimplementierungen stellen jeweils eine Funktion bereit, welche die Position eines Elementes in einer Liste bestimmt.
Iterativ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #!/usr/bin/env python
def binSuche(elemente, element):
left = 0
right = len(elemente)
while left <= right:
center = (left+right)/2
if elemente[center] == element:
return center
if elemente[center] > element:
right = center-1
if elemente[center] < element:
left = center+1
return -1
if __name__ == "__main__":
elemente = range(10)
print binSuche(elemente, 5)
|
Rekursiv
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #!/usr/bin/env python
def binSucheRec(elemente, element, left=0, right=None):
if not right:
right = len(elemente)
if left > right:
return -1
center = (left+right)/2
if elemente[center] == element:
return center
if elemente[center] > element:
return binSucheRec(elemente, element, left, center-1)
if elemente[center] < element:
return binSucheRec(elemente, element, center+1, right)
if __name__ == "__main__":
elemente = range(10)
print binSucheRec(elemente, 5)
|
Implementierung in C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <stdio.h>
#include <stdlib.h>
int binSearch(int** list, int count, int search) {
int center;
int left = 0;
int right = count-1;
while(left<=right) {
center = (left+right)/2;
if(list[center] == search)
return center;
if(list[center] > search)
right = center-1;
if(list[center] < search)
left = center+1;
}
return -1;
}
int main() {
// ordered list of items
int items[] = { 0x01, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0F,
0x10, 0x15, 0x1C, 0x1E, 0x23, 0x24, 0x25,
0x27, 0x2B, 0x2C, 0x3A, 0x3B, 0x3D };
// search element 0x07
int index = binSearch(&items;, sizeof(items)/sizeof(int), 0x07);
printf("found at index %d\n", index);
return 0;
}
|
Post comment
Zum Kommentieren musst du angemeldet sein.
0 comments
Sorry but there are no comments for this entry. What about writing the first one?