Επεξήγηση γραμμικής αναζήτησης

Τι είναι η Γραμμική αναζήτηση;

Ας υποθέσουμε ότι σας έχει δοθεί μια λίστα ή μια σειρά αντικειμένων. Ψάχνετε για ένα συγκεκριμένο αντικείμενο. Πώς το κάνεις αυτό;

Βρείτε τον αριθμό 13 στη δεδομένη λίστα.

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

Απλώς κοιτάς τη λίστα και αυτό είναι!

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

Τώρα, πώς λέτε σε έναν υπολογιστή να τον βρει;

Ένας υπολογιστής δεν μπορεί να κοιτάξει περισσότερο από την τιμή σε μια δεδομένη στιγμή. Παίρνει λοιπόν ένα στοιχείο από τον πίνακα και ελέγχει αν είναι το ίδιο με αυτό που ψάχνετε.

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

Το πρώτο στοιχείο δεν ταιριάζει. Συνεχίστε λοιπόν στο επόμενο.

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

Και ούτω καθεξής…

Αυτό γίνεται μέχρι να βρεθεί ένας αγώνας ή μέχρι να ελεγχθούν όλα τα αντικείμενα.

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

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

Λοιπόν, πόσο καιρό θα χρειαστεί για να γίνει η γραμμική λειτουργία αναζήτησης Στην καλύτερη περίπτωση, θα μπορούσατε να είστε τυχεροί και το αντικείμενο που εξετάζετε ίσως στην πρώτη θέση του πίνακα!

Αλλά στη χειρότερη περίπτωση, θα πρέπει να κοιτάξετε κάθε στοιχείο πριν βρείτε το στοιχείο στην τελευταία θέση ή προτού συνειδητοποιήσετε ότι το στοιχείο δεν βρίσκεται στον πίνακα.

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

Εάν το στοιχείο προς αναζήτηση ζούσε στο πρώτο μπλοκ μνήμης, τότε η πολυπλοκότητα θα ήταν: O (1).

Ο κώδικας για μια γραμμική λειτουργία αναζήτησης σε JavaScript εμφανίζεται παρακάτω. Αυτή η συνάρτηση επιστρέφει τη θέση του αντικειμένου που αναζητούμε στον πίνακα. Εάν το στοιχείο δεν υπάρχει στον πίνακα, η συνάρτηση θα επιστρέψει null.

Παράδειγμα σε Javascript

function linearSearch(arr, item) { // Go through all the elements of arr to look for item. for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { // Found it! return i; } } // Item not found in the array. return null; }

Παράδειγμα στο Ruby

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end

Παράδειγμα στο C ++

int linear_search(int arr[],int n,int num) { for(int i=0;i
    

Example in Python

def linear_search(array, num): for i in range(len(array)): if (array[i]==num): return i return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

  • How to implement quick sort
  • Binary search algorithm
  • Jump search algorithm
  • Search algorithms explained with examples
  • Implement a binary search algorithm in Java without recursion
  • More info on search algorithms