Линейный поиск — ProgrammingTasks

Этот вид поиска является самым простым и заключается в последовательном просмотре элементов массива, пока не будет найден искомый элемент.

В случае отсутствия искомого элемента метод возвращает некоторое фиксированное значение, например, -1 или false.

В худшем случае придется просмотреть все элементы массива, таким образом, его асимптотическая сложность составляет O(N).

Далее представлен алгоритм линейного поиска на разных языках программирования.

#include <stdio.h>

int linear_search(const int ar[], int length, int item)
{
    int i = 0;
    while (i < length && ar[i] != item)
        i++;
    if (i < length)
        return i;
    else
        return -1;
}

int main(void)
{
   int arr[] = { 1,2,3,4,5 };
   int length = sizeof(arr) / sizeof(*arr);
   int search_item = 10;
   int foundindex = linear_search(arr, length, search_item);

   printf("search: %d, res=%d\n", search_item, foundindex);

   return 0;
}

internal class Program
{
    static int LinearSearch(T[] arr, T item) where T : IComparable
    {
        int i = 0;
        int length = arr.Length;
        
        while(i < length && arr[i].CompareTo(item)!=0) 
        {
            i++;
        }

        if (i<length)
        {
            return i;
        }

        return -1;
    }

    static void Main(string[] args)
    {
        int[] arr1 = { 5, 12, 3, 8 , 4, 7 };
        int item = 4;
        int index=LinearSearch(arr1, item);

        Console.WriteLine($"Array: {String.Join(" ", arr1)}\nitem = {item}, index = {index}");
        Console.ReadKey();
    }
}

<?php

function LinearSearch(array $arr, int $item): int
{
    $i=0;
    $length=count($arr);

    while($i<$length && $arr[$i]!=$item) {
        $i++;
    }

    if ($i<$length) {
        return $i;
    }

    return -1;
}

function LinearSearch(arr, item) {
    if (Array.isArray(arr)) {
       let i=0;
       const len=arr.length;

       while(i<len && arr[i]!==item) {
            i++;
       }

       if (i<len) {
          return i;
       }

       return -1;
    }
    else {
        throw new Error("First argument must be of type Array");
    }
}