Să presupunem că vi se oferă o listă sau o serie de articole. Căutați un anumit articol. Cum faci asta?

Găsiți numărul 13 în lista dată.

Căutare liniară 1

Te uiți doar la listă și iată-o!

Căutare liniară 2

Acum, cum îi spui unui computer să îl găsească?

Citește mai multCum se face o promisiune dintr-o funcție de apel invers în JavaScript

Un computer nu poate privi mai mult decât valoarea la un moment dat de timp. Deci, ia un element din matrice și verifică dacă este același lucru cu ceea ce căutați.

Căutare liniară 3

Primul articol nu s-a potrivit. Așa că treceți la următorul.

Căutare liniară 4

Si asa mai departe…

Acest lucru se face până când se găsește o potrivire sau până când toate articolele au fost verificate.

Căutare liniară 5

În acest algoritm, vă puteți opri atunci când elementul este găsit și atunci nu este nevoie să căutați mai departe.

Citește mai multCum se generează un fișier de reducere GitHub din Microsoft Word utilizând TypeScript

Deci, cât ar dura până se face operația de căutare liniară? În cel mai bun caz, ați putea avea noroc, iar elementul la care vă uitați poate poate la prima poziție din matrice!

Dar, în cel mai rău caz, ar trebui să te uiți la fiecare articol înainte de a găsi articolul la ultimul loc sau înainte de a-ți da seama că articolul nu este în matrice.

Prin urmare, complexitatea căutării liniare este O (n).

Dacă elementul de căutat ar trăi pe primul bloc de memorie, atunci complexitatea ar fi: O (1).

Codul pentru o funcție de căutare liniară în JavaScript este prezentat mai jos. Această funcție returnează poziția elementului pe care îl căutăm în matrice. Dacă elementul nu este prezent în matrice, funcția va reveni la nul.

Exemplu în 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;
}

Exemplu în 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

Exemplu în C ++

int linear_search(int arr[],int n,int num)
{
	for(int i=0;i<n;i++){
		if(arr[i]==num)
			return i;
   }
   // Item not found in the array
   return -1; 
}

Exemplu în Python

def linear_search(array, num):
	for i in range(len(array)):
		if (array[i]==num):
			return i
	return -1
Citește mai multAutentificare utilizând Google în ASP.NET Core 2.0

Ce se întâmplă dacă căutați aparițiile multiple ale unui element? De exemplu, doriți să vedeți câte 5 sunt într-o matrice.

Țintă = 5

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

Această matrice are 3 apariții de 5s și dorim să returnăm indexurile (unde sunt în matrice) ale tuturor acestora.

Aceasta se numește căutare liniară globală și va trebui să vă ajustați codul pentru a returna o serie de puncte index în care găsește elementul dvs. țintă.

Când găsiți un element index care se potrivește țintei dvs., punctul index (contor) va fi adăugat în matricea de rezultate. Dacă nu se potrivește, codul va continua să treacă la următorul element din matrice adăugând 1 la contor.

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

De ce căutarea liniară nu este eficientă

Nu există nicio îndoială că căutarea liniară este simplă. Dar, deoarece compară fiecare element unul câte unul, este consumator de timp și, prin urmare, nu este foarte eficient. Dacă trebuie să găsim un număr din, să zicem, 1.000.000 de numere și acest număr se află pe ultima poziție, o tehnică de căutare liniară ar deveni destul de obositoare.

Deci, ar trebui să aflați și despre sortarea cu bule, sortarea rapidă și alți algoritmi mai eficienți.

Alți algoritmi de căutare: