Алгоритм линейного поиска и его реализация на C

Линейный поиск — это алгоритм последовательного поиска.

В этом алгоритме ключевой элемент ищется в заданном входном массиве в последовательном порядке.

Если ключевой элемент найден во входном массиве, он возвращает элемент.

Алгоритм линейного поиска

Linear_Search (массив 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

Реализация линейного поиска в C

Изначально нам нужно указать или принять элемент для поиска от пользователя.
Затем мы создаем цикл for и начинаем последовательный поиск элемента.
Как только компилятор обнаружит совпадение, т. е. массив[элемент] == ключевое значение, вернет элемент вместе с его позицией в массиве.
Если не найдено значений, соответствующих входным данным, возвращается -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.

Заключение

Таким образом, в этой статье мы поняли и реализовали алгоритм линейного поиска.