Рубрики

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

Проблема: Учитывая массив arr [] из n элементов, напишите функцию для поиска данного элемента x в arr [].

Примеры :

Input : arr[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
          x = 110;
Output : 6
Element x is present at index 6

Input : arr[] = {10, 20, 80, 30, 60, 50, 
                     110, 100, 130, 170}
           x = 175;
Output : -1
Element x is not present in arr[].

Простым подходом является линейный поиск , т.е.

  • Начните с самого левого элемента arr [] и сравнивайте один за другим x с каждым элементом arr []
  • Если x соответствует элементу, вернуть индекс.
  • Если x не совпадает ни с одним из элементов, вернуть -1.


Пример:

C ++

// C ++ код для линейного поиска x в arr []. Если х
// присутствует, затем возвращает свое местоположение, в противном случае
// возвращаем -1

  
#include <iostream>

using namespace std;

  

int search(int arr[], int n, int x)

{

    int i;

    for (i = 0; i < n; i++)

        if (arr[i] == x)

            return i;

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int x = 10;

    int n = sizeof(arr) / sizeof(arr[0]);

    int result = search(arr, n, x);

   (result == -1)? cout<<"Element is not present in array" 

                 : cout<<"Element is present at index " <<result;

   return 0;

}

С

// C ++ код для линейного поиска x в arr []. Если х
// присутствует, затем возвращает свое местоположение, в противном случае
// возвращаем -1

  
#include <stdio.h>

  

int search(int arr[], int n, int x)

{

    int i;

    for (i = 0; i < n; i++)

        if (arr[i] == x)

            return i;

    return -1;

}

  

int main(void)

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int x = 10;

    int n = sizeof(arr) / sizeof(arr[0]);

    int result = search(arr, n, x);

    (result == -1) ? printf("Element is not present in array")

                   : printf("Element is present at index %d",

                            result);

    return 0;

}

Джава

// Java-код для линейного поиска x в arr []. Если х
// присутствует, затем возвращает свое местоположение, в противном случае
// возвращаем -1

  

class GFG 

public static int search(int arr[], int x)

{

    int n = arr.length;

    for(int i = 0; i < n; i++)

    {

        if(arr[i] == x)

            return i;

    }

    return -1;

}

  

public static void main(String args[])

{

    int arr[] = { 2, 3, 4, 10, 40 }; 

    int x = 10;

      

    int result = search(arr, x);

    if(result == -1)

        System.out.print("Element is not present in array");

    else

        System.out.print("Element is present at index " + result);

}
}

python3

# Python3 код для линейного поиска x в arr [].
# Если x присутствует, вернуть его местоположение,
# иначе вернуть -1

  

def search(arr, n, x):

  

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1;

  
Код водителя

arr = [ 2, 3, 4, 10, 40 ];

x = 10;

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("Element is not present in array")

else:

    print("Element is present at index", result);

C #

// C # код для линейного поиска x в arr []. Если х
// присутствует, затем возвращает свое местоположение, в противном случае
// возвращаем -1

using System; 

  

class GFG 

    public static int search(int[] arr, int x)

    {

        int n = arr.Length;

        for(int i = 0; i < n; i++)

        {

            if(arr[i] == x)

                return i;

        }

        return -1;

    }

      

    public static void Main()

    {

        int[] arr = { 2, 3, 4, 10, 40 }; 

        int x = 10;

          

        int result = search(arr, x);

        if(result == -1)

            Console.WriteLine("Element is not present in array");

        else

            Console.WriteLine("Element is present at index "+ result);

    }

}

  
// Этот код предоставлен DrRoot_

PHP

<?php
// PHP-код для линейного поиска x в arr [].
// Если x присутствует, вернуть его местоположение,
// в противном случае возвращаем -1

  

function search($arr, $x)

{

    $n = sizeof($arr);

    for($i = 0; $i < $n; $i++)

    {

        if($arr[$i] == $x)

            return $i;

    }

    return -1;

}

  
// Код драйвера

$arr = array(2, 3, 4, 10, 40); 

$x = 10;

      

$result = search($arr, $x);

if($result == -1)

    echo "Element is not present in array";

else

    echo "Element is present at index " ,

                                 $result;

  
// Этот код добавлен
// от jit_t
?>

Выход:

Element is present at index 3

Временная сложность вышеприведенного алгоритма составляет O (n).

Линейный поиск редко используется практически, потому что другие алгоритмы поиска, такие как алгоритм двоичного поиска и хеш-таблицы, позволяют значительно быстрее сравнивать поиск с линейным поиском.

Также смотрите — Бинарный поиск

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes