Линеарно пребарување алгоритам и имплементација во C

Линеарното пребарување во основа е секвенцијален алгоритам за пребарување.

Во овој алгоритам, клучниот елемент се пребарува во дадената влезна низа по секвенцијален редослед.

Ако клучниот елемент се најде во влезната низа, тој го враќа елементот.

Алгоритам за линеарно пребарување

Линеарно_пребарување ( Низа X, вредност i)

• Поставете j на 1
• Ако j > n, скокнете на чекор 7
• Ако X[j] == i, префрлете се на чекор 6
• Потоа, зголемување j за 1 т.е. j=j+1
• Вратете се на чекор 2
• Прикажи го елементот i кој се наоѓа на одреден индекс i, а потоа прескокнете на чекор 8
• Елементот за приказ не е пронајден во множеството влезни елементи.
• Излез/Крај

Псевдо код за линеарно пребарување

procedure LINEAR_SEARCH (array, key)

   for each item in the array
      if match element == key
         return element's index
      end if
   end for

end procedure

Имплементација на линеарно пребарување во В

• Првично, треба да го споменеме или прифатиме елементот што треба да се пребарува од корисникот.
• Потоа, создаваме јамка за и почнуваме да го бараме елементот на секвенцијален начин.
• Штом компајлерот ќе наиде на совпаѓање, т.е. низа[елемент] == клучна вредност, вратете го елементот заедно со неговата позиција во низата.
• Ако не се најдат вредности што одговараат на влезот, тој враќа -1.

#include <stdio.h> 

int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 


int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
    else
    printf("Item is present at index %d", res);
    
	return 0; 
} 

Излез:

Item is present at index 5

Временска сложеност на линеарното пребарување

Комплексноста во најдобар случај е O(1) ако елементот се најде во првата итерација на јамката.

временската сложеност во најлош случај е O(n), ако елементот за пребарување се најде на крајот од низата, под услов големината на низата да биде n.

Заклучок

Така, во оваа статија го разбравме и имплементиравме Линеарно пребарување алгоритам.