Σε αυτό το σεμινάριο, θα μάθετε για τη γραμμική αναζήτηση. Επίσης, θα βρείτε λειτουργικά παραδείγματα γραμμικής αναζήτησης C, C ++, Java και Python.
Η γραμμική αναζήτηση είναι ο απλούστερος αλγόριθμος αναζήτησης που αναζητά ένα στοιχείο σε μια λίστα με διαδοχική σειρά. Ξεκινάμε από το ένα άκρο και ελέγχουμε κάθε στοιχείο έως ότου δεν βρεθεί το επιθυμητό στοιχείο.
Πώς λειτουργεί η Γραμμική Αναζήτηση;
Τα παρακάτω βήματα ακολουθούνται για να αναζητήσετε ένα στοιχείο k = 1στην παρακάτω λίστα.
Πίνακας για αναζήτηση
- Ξεκινήστε από το πρώτο στοιχείο, συγκρίνετε k με κάθε στοιχείο x.
Συγκρίνετε με κάθε στοιχείο - Εάν
x == k, επιστρέψτε το ευρετήριο.
Βρέθηκε στοιχείο - Αλλιώς, η επιστροφή δεν βρέθηκε.
Γραμμικός αλγόριθμος αναζήτησης
LinearSearch (πίνακας, κλειδί) για κάθε στοιχείο του πίνακα εάν η τιμή item == επιστρέφει το ευρετήριό της
Παραδείγματα Python, Java και C / C ++
Python Java C C ++ # Linear Search in Python def linearSearch(array, n, x): # Going through array sequencially for i in range(0, n): if (array(i) == x): return i return -1 array = (2, 4, 0, 1, 9) x = 1 n = len(array) result = linearSearch(array, n, x) if(result == -1): print("Element not found") else: print("Element found at index: ", result)
// Linear Search in Java class LinearSearch ( public static int linearSearch(int array(), int x) ( int n = array.length; // Going through array sequencially for (int i = 0; i < n; i++) ( if (array(i) == x) return i; ) return -1; ) public static void main(String args()) ( int array() = ( 2, 4, 0, 1, 9 ); int x = 1; int result = linearSearch(array, x); if (result == -1) System.out.print("Element not found"); else System.out.print("Element found at index: " + result); ) )
// Linear Search in C #include int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result); )
// Linear Search in C++ #include using namespace std; int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result; )
Γραμμικές πολυπλοκότητες αναζήτησης
Χρόνος πολυπλοκότητας: O (n)
Διαστημική πολυπλοκότητα: O(1)
Εφαρμογές γραμμικής αναζήτησης
- Για εργασίες αναζήτησης σε μικρότερες σειρές (<100 αντικείμενα).
