Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α17.10 · Η συνάρτηση what

Εξέταση Σεπτεμβρίου 2024, Θέμα 2 · Δυσκολία ★☆☆ · trace · Κεφάλαια: 17

Η συνάρτηση what (10 Μονάδες)

int what(int *array, int x, int y) {
  int mid, low = 0, high = y - 1;
  while (low <= high) {
    mid = low + (high - low) / 2;
    printf("%d\n", mid);
    if (array[mid] == x) return 1;
    else if (array[mid] < x) low = mid + 1;
    else high = mid - 1;
  }
  return 0;
}

Τι κάνει η συνάρτηση what (μέχρι 10 λέξεις εξήγηση); Τι θα τυπώσει αν κληθεί με ορίσματα {57, 98, 105, 241}, 36, 4;

Υπόδειξη

Αναγνωρίστε το μοτίβο: δύο όρια low/high που πλησιάζουν μεταξύ τους και ένα μεσαίο στοιχείο που συγκρίνεται με το x. Για την έξοδο, κρατήστε έναν πίνακα με τις τιμές low, high, mid σε κάθε επανάληψη και προσέξτε ότι το 36 είναι μικρότερο από όλα τα στοιχεία του πίνακα.

Αριθμός στον οδηγό: Α17.10 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2024-sep-q2 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-sep-q2.html · Markdown (GitHub)