searching [Algoritmi si Tehnici de Programare - C] Algoritmul de Cautare Liniar

[King Of Underground]

** Analiza Algoritmilor **

Algoritmii sunt modalitati de identificare si rezolvare a unei sau mai multe probleme . In rezolvarea unei probleme , pot exista mai multe solutii dar unele pot fi mai eficiente sau nu . Eficacitatea unui algoritm este masurata in TIMP SI SPATIU . 

* TIMPUL CONSTA IN PERIOADA DE EXECUTIE A ALGORITMULUI . CU CAT TINDE SPRE 0 , cu atat este mult mai eficient din acest aspect  !! 

* SPATIUL CONSTA IN RESURSELE ALOCATE IN EXECUTAREA ALGORITMULUI . CU CAT SPATIUL ESTE MAI MIC , CU ATAT ALGORITMUL ESTE MAI EFICIENT !!

** Introducere in Algoritmii de Cautare ** 

Algoritmii de cautare reprezinta modalitati diferite de rezolvare a problemei privind cautarea unui element sau mai multe ,

 intr-o colectie (array,liste,arbori etc.) . 

Importanta algoritmilor de cautare :

• Ne ajuta la cautarea unui produs sau persoana , dupa preferintele noastre ,  de pe un site de e-commerce sau social media (persoana) ;
• Ne ajuta in  diferite sisteme de recunoastere vocala , faciala etc. ;
• Ne ajuta sa cautam relevant intr o baza de date ;
• Ne ajuta la aflarea rutei optime dintr - o retea etc. 

** Algoritmul de Cautare Liniar **

Cautarea Liniara reprezinta cea mai usoara modalitate de a descoperi un termen dintr- o colectie . Ea consta in verificarea fiecarui element in parte , de la un cap la celalalt . 

Explicatie : 

   Definim o colectie de 10 numere . Sa cautam termenul 30 in colectie : 
   
   [40 , 50 , 35 , 60 , 70 , 78 , 30 , 10 , 5 , 12]
   
   Navigam prin colectie si luam la comparatie fiecare numar (de la cifra 40 pana la 30)
   
   40 diferit de 30 ==> mergem la urmatorul 
   50 diferit de 30 ==> mergem la urmatorul 
   35 diferit de 30 ==> mergem la urmatorul 
   60 diferit de 30 ==> mergem la urmatorul 
   70 diferit de 30 ==> mergem la urmatorul 
   78 diferit de 30 ==> mergem la urmatorul 
   30 egal cu 30    ==> TERMEN GASIT , OPRIM ALGORITMUL !!! 

Interpretare algoritm in C : 

 

#include <stdio.h>


int main()
{
	int a[10];
	
	printf("Insereaza 10 numere : \n");

		for (int i = 0; i < 10; i++)
		{
			printf("colectie[%d] = ",i);
			scanf_s("%d", &a[i]);  // Inseram numerele de la tastatura 
		
		}

		int numberToSearch, found = 0, index;

		do {
			printf("Insereaza numarul pe care vrei sa l cauti in colectie : ");
			scanf_s("%d", &numberToSearch);

			for (int i = 0; i < 10; i++)  // Navigam prin colectie 
			{
				if (numberToSearch == a[i])  // Cautam secvential prin toata colectia si comparam cu fiecare individ
				{
					// DACA S -A IMPLINIT CONDITIA DE MAI SUS 

					found = 1; // Am gasit elementul 
					index = i; // Salvam indexul 
					break; // Intrerupem bucla !! 
				}
			}

			printf("\n");

		} while (found == 0);


		printf("Am gasit elementul %d la pozitia %d", numberToSearch, index); 


	return 0;
}

NOTA 1 ** : Algoritmul devine mai ineficient cu cat elementul cautat este mai aproape de capat (TIMPUL DE EXECUTIE DEVINE DIN CE IN CE MAI MARE !!)

NOTA 2 ** : NU SE RECOMANDA ACEST ALGORITM DE CAUTARE CAND AVEM DE A FACE CU COLECTII DE MARI DIMENSIUNI SAU ORDONATE !!!