Εφαρμογές αλγορίθμων αναζήτησης στην Python

από
Tweet
Share
Share
Pin

Η εφαρμογή της αναζήτησης είναι πάντα δύσκολη αλλά όχι αδύνατη.

Στην πραγματική ζωή, δεν θα ψάξουμε χωρίς μοτίβο. Απλώς πηγαίνουμε στα μέρη όπου πιστεύουμε ότι μπορεί να τοποθετηθεί. Δεν ακολουθούμε κανένα μοτίβο στις περισσότερες περιπτώσεις.

Λειτουργεί το ίδιο πράγμα στον κόσμο του προγραμματισμού;

Οχι! πρέπει να υπάρχει κάποιο μοτίβο για να αναζητήσετε πράγματα σε προγράμματα. Θα δούμε μερικούς αλγόριθμους που ακολουθούν διαφορετικά μοτίβα αναζήτησης σε αυτό το άρθρο.

Υπάρχουν πολλοί αλγόριθμοι που μπορούμε να βρούμε στον κόσμο του προγραμματισμού. Θα συζητήσουμε τους πιο σημαντικούς και περισσότερο χρησιμοποιούμενους αλγόριθμους σε αυτό το άρθρο. Και οι υπόλοιποι αλγόριθμοι θα είναι ένα κομμάτι κέικ για να μάθετε.

Η αναζήτηση αναφέρεται στην αναζήτηση ενός στοιχείου στον πίνακα σε αυτό το άρθρο.

Ας τα δούμε ένα προς ένα.

Γραμμική αναζήτηση

Το όνομα υποδηλώνει ότι ο αλγόριθμος γραμμικής αναζήτησης ακολουθεί το γραμμικό μοτίβο για την αναζήτηση των στοιχείων σε έναν πίνακα. Ο αλγόριθμος ξεκινά την αναζήτηση του στοιχείου από την αρχή του πίνακα και μετακινείται στο τέλος μέχρι να βρει το στοιχείο. Σταματά την εκτέλεση του προγράμματος όταν βρει το απαιτούμενο στοιχείο.

Ας παρουσιάσουμε τους αλγόριθμους γραμμικής αναζήτησης με μερικές ενδιαφέρουσες εικόνες για καλύτερη κατανόηση του αλγορίθμου.

Εάν παρατηρήσετε προσεκτικά το μοτίβο αναζήτησης, θα διαπιστώσετε ότι ο χρόνος που χρειάζεται για την εκτέλεση του προγράμματος θα πάρει O(n) στη χειρότερη περίπτωση. Πρέπει να λάβουμε υπόψη τη χειρότερη χρονική πολυπλοκότητα των αλγορίθμων προς ανάλυση. Ως εκ τούτου, η χρονική πολυπλοκότητα του αλγορίθμου είναι O(n).

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

Υλοποίηση Γραμμικής Αναζήτησης

Τώρα, έχετε μια καλή κατανόηση του αλγόριθμου γραμμικής αναζήτησης. Ήρθε η ώρα να λερώσουμε τα χέρια μας με κάποιο κωδικό. Ας δούμε πρώτα τα βήματα για την υλοποίηση της γραμμικής αναζήτησης. Μετά προσπαθείς να το κωδικοποιήσεις. Μην ανησυχείτε ακόμα κι αν δεν μπορείτε. Θα σας δώσω τον κωδικό μετά.

  Κορυφαία Metaverse Crypto Coins προς αγορά

Ας δούμε τα βήματα για την εφαρμογή του αλγόριθμου γραμμικής αναζήτησης.

  • Αρχικοποιήστε μια σειρά στοιχείων (τους τυχερούς σας αριθμούς).
  • Γράψτε μια συνάρτηση που ονομάζεται search_element, η οποία δέχεται τρία ορίσματα, πίνακα, μήκος του πίνακα και στοιχείο προς αναζήτηση.
  • search_element(arr, n, element):
    • Επανάληψη πάνω από τον δεδομένο πίνακα.
      • Ελέγξτε εάν το τρέχον στοιχείο είναι ίσο με το απαιτούμενο στοιχείο.
      • Εάν ναι, τότε επιστρέψτε το True.
    • Μετά την ολοκλήρωση του βρόχου, εάν η εκτέλεση εξακολουθεί να είναι στη συνάρτηση, τότε το στοιχείο δεν υπάρχει στον πίνακα. Επομένως, επιστρέψτε το False.
  • Εκτυπώστε το μήνυμα με βάση την τιμή επιστροφής της συνάρτησης search_element.

Τέλος, γράψτε τον κώδικα με τη βοήθεια των παραπάνω βημάτων για να εφαρμόσετε τον αλγόριθμο γραμμικής αναζήτησης.

Ολοκληρώσατε την υλοποίηση του αλγορίθμου γραμμικής αναζήτησης; Το ελπίζω. Εάν ολοκληρώσατε, τότε διασταυρώστε τον παρακάτω κωδικό.

Αν δεν το ολοκληρώσατε, μην ανησυχείτε. δείτε τον παρακάτω κώδικα και μάθετε πώς τον εφαρμόσαμε. Θα το αποκτήσετε χωρίς πολλή προσπάθεια.

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Αρχικά, εκτελέστε το πρόγραμμα με ένα στοιχείο που υπάρχει στον πίνακα. Και στη συνέχεια, εκτελέστε το με ένα στοιχείο που δεν υπάρχει στον πίνακα.

Η χρονική πολυπλοκότητα του αλγορίθμου γραμμικής αναζήτησης είναι O(n).

Μπορούμε να το μειώσουμε λίγο περισσότερο με διαφορετικά μοτίβα;

Ναι, μπορούμε. Ας το δούμε.

Δυαδική αναζήτηση

Ο αλγόριθμος δυαδικής αναζήτησης ελέγχει πάντα το μεσαίο στοιχείο του πίνακα. Αυτός ο αλγόριθμος αναζητά το στοιχείο σε έναν ταξινομημένο πίνακα.

Ο δυαδικός αλγόριθμος αναζήτησης επαναλαμβάνεται πάνω από τον πίνακα και ελέγχει το μεσαίο στοιχείο, εάν βρεθεί, και μετά σταματά το πρόγραμμα. Διαφορετικά, αν το μεσαίο στοιχείο είναι μικρότερο από το απαιτούμενο στοιχείο, τότε παραλείπει από την αναζήτηση το αριστερό μέρος του πίνακα από το μεσαίο στοιχείο. Διαφορετικά, αν το μεσαίο στοιχείο είναι μεγαλύτερο από το απαιτούμενο στοιχείο, τότε παραλείπει από την αναζήτηση το δεξί μέρος του πίνακα από το μεσαίο στοιχείο.

  Ένας οδηγός για τη ρύθμιση παραμέτρων και πώς να το αποτρέψετε

Σε κάθε επανάληψη, ο αλγόριθμος δυαδικής αναζήτησης μειώνει την περιοχή για να αναζητήσει το στοιχείο. Έτσι, ο αριθμός των ελέγχων είναι μικρότερος από τον αριθμό των ελέγχων που έγιναν στον αλγόριθμο γραμμικής αναζήτησης.

Οι απεικονίσεις μας βοηθούν να κατανοήσουμε καλύτερα τον αλγόριθμο δυαδικής αναζήτησης. Ας τα ελέγξουμε.

Η χρονική πολυπλοκότητα του δυαδικού αλγορίθμου αναζήτησης είναι O(log n). Σε κάθε επανάληψη, το μήκος της περιοχής αναζήτησης μειώνεται κατά το ήμισυ. Μειώνεται εκθετικά.

Εφαρμογή δυαδικής αναζήτησης

Αρχικά, θα δούμε τα βήματα για την υλοποίηση του δυαδικού αλγόριθμου αναζήτησης και μετά τον κώδικα. Ας δούμε τα βήματα για την ολοκλήρωση της υλοποίησης του δυαδικού αλγορίθμου αναζήτησης.

  • Αρχικοποιήστε τον πίνακα με στοιχεία (οι τυχεροί σας αριθμοί)
  • Γράψτε μια συνάρτηση που ονομάζεται search_element, η οποία δέχεται τρία ορίσματα, ταξινομημένο πίνακα, μήκος του πίνακα και στοιχείο προς αναζήτηση.
  • search_element(sorted_arr, n, element):
    • Αρχικοποιήστε τη μεταβλητή ευρετηρίου i για επανάληψη πίνακα.
    • Στη συνέχεια, αρχικοποιήστε δύο μεταβλητές για να διατηρήσετε την περιοχή αναζήτησης του πίνακα. Εδώ, τα ονομάζουμε ως αρχή και τέλος καθώς υποδεικνύουν ευρετήρια.
    • Επαναλάβετε μέχρι το i να είναι μικρότερο από το μήκος του πίνακα.
      • Υπολογίστε το μεσαίο ευρετήριο της περιοχής αναζήτησης χρησιμοποιώντας τις τιμές έναρξης και τέλους. Αυτό θα είναι (έναρξη + τέλος) // 2.
      • Ελέγξτε εάν το μεσαίο ευρετήριο στοιχείο από την περιοχή αναζήτησης είναι ίσο με το απαιτούμενο στοιχείο ή όχι.
      • Εάν ναι, τότε επιστρέψτε το True.
      • Διαφορετικά, εάν το μεσαίο ευρετήριο στοιχείο είναι μικρότερο από το απαιτούμενο στοιχείο, τότε μετακινήστε το αρχικό ευρετήριο της περιοχής αναζήτησης στη μέση + 1.
      • Διαφορετικά, εάν το μεσαίο ευρετήριο στοιχείο είναι μεγαλύτερο από το απαιτούμενο στοιχείο, τότε μετακινήστε το τελικό ευρετήριο της περιοχής αναζήτησης στη μέση – 1.
      • Αύξηση του δείκτη του πίνακα i.
    • Μετά την ολοκλήρωση του βρόχου, εάν η εκτέλεση εξακολουθεί να είναι στη συνάρτηση, τότε το στοιχείο δεν υπάρχει στον πίνακα. Επομένως, επιστρέψτε το False.
  • Εκτυπώστε το μήνυμα με βάση την τιμή επιστροφής της συνάρτησης search_element.
  Πώς να βρείτε τον σύνδεσμο άμεσης λήψης σε οποιοδήποτε αρχείο

Προσπαθήστε να γράψετε τον κώδικα παρόμοιο με την υλοποίηση του αλγορίθμου γραμμικής αναζήτησης.

…

Πήρες τον κωδικό;

Ναι, συγκρίνετε το με τον παρακάτω κώδικα. Όχι, μην ανησυχείς. κατανοήσετε την υλοποίηση με τον παρακάτω κώδικα.

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Δοκιμάστε τον κώδικα με διαφορετικές περιπτώσεις όπου το στοιχείο είναι παρόν και δεν υπάρχει σε ορισμένες περιπτώσεις.

συμπέρασμα

Ο αλγόριθμος δυαδικής αναζήτησης είναι πολύ πιο αποτελεσματικός από τον αλγόριθμο γραμμικής αναζήτησης. Πρέπει να ταξινομήσουμε τον πίνακα για τον αλγόριθμο δυαδικής αναζήτησης δεν συμβαίνει στον αλγόριθμο γραμμικής αναζήτησης. Η ταξινόμηση απαιτεί λίγο χρόνο. Ωστόσο, η χρήση αποδοτικών αλγορίθμων για ταξινόμηση θα αποτελέσει έναν καλό συνδυασμό με τον αλγόριθμο δυαδικής αναζήτησης.

Τώρα, έχετε καλή γνώση των πιο ευρέως χρησιμοποιούμενων αλγορίθμων στην Python.

Στη συνέχεια, μάθετε μερικά από τα δημοφιλή αυτο-φιλοξενούμενα λογισμικά αναζήτησης.

Καλή κωδικοποίηση 🙂 🧑‍💻