Τρίτη, 8 Μαΐου 2012

Υλοποίηση της ακολουθιακής και της δυαδικής αναζήτησης με επαναληπτικό τρόπο.

Ακολουθιακή αναζήτηση.
Αυτός ο αλγόριθμος ελέγχει αν ο αριθμός v περιλαμβάνεται σε ένα ήδη αποθηκευμένο σύνολο αριθμών στα στοιχεία a[0], a[1], …, a[r-1] του πίνακα a (όπου r ο αριθμός των στοιχείων σε αυτόν), συγκρίνοντας τον με κάθε αριθμό ακολουθιακά, ξεκινώντας από την αρχή. Εάν ο έλεγχος φθάσει στο τέλος χωρίς να βρεθεί ο αριθμός, επιστρέφεται η τιμή -1. Διαφορετικά, επιστρέφεται ο αριθμοδείκτης της θέσης του μονοδιάστατου πίνακα που περιέχει τον αριθμό.

int
search (int a[], int v, int r) {
  for (int i = 0; i < r; i++)
    if (v == a[i])
      return i;

    return -1;
}
Δυαδική αναζήτηση.
Αυτός ο αλγόριθμος ελέγχει αν ο αριθμός v περιλαμβάνεται σε ένα ήδη αποθηκευμένο σύνολο αριθμών στα στοιχεία a[0], a[1], …, a[r-1] του πίνακα a, όπου r ο αριθμός των στοιχείων σε αυτόν. Εάν ο έλεγχος φθάσει στο τέλος χωρίς να βρεθεί ο αριθμός, επιστρέφεται η τιμή -1. Διαφορετικά, επιστρέφεται ο αριθμοδείκτης της θέσης του μονοδιάστατου πίνακα που περιέχει τον αριθμό. Για να λειτουργήσει σωστά η δυαδική αναζήτηση θα πρέπει πρώτα τα στοιχεία του πίνακα να είναι ταξινομημένα σε αύξουσα σειρά.
int
search (int a[], int v, int r) {
  int l = 0;
  while (r - l > 1) {
    int m = l + (r - l) / 2;

    if (a[m] > v)
      r = m;
    else
      l = m;
  }

  return (a[l] == v) ? l : -1;
}

Δεν υπάρχουν σχόλια: