Pesquisa Linear
Problema: Dado um array arr [] de n elementos, escreva uma função para pesquisar um dado elemento x em arr [].
Exemplos :
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[].
Uma abordagem simples é fazer uma pesquisa linear , ou seja,
- Comece a partir do elemento mais à esquerda de arr [] e, um por um, compare x com cada elemento de arr []
- Se x corresponde a um elemento, retorna o índice.
- Se x não corresponder a nenhum dos elementos, retorne -1.
Exemplo:
// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -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;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
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 code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -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;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
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 code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -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;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
// Function call
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 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1
def search(arr, n, x):
for i in range(0, n):
if (arr[i] == x):
return i
return -1
# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)
# Function call
result = search(arr, n, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)// C# code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -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;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int x = 10;
// Function call
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);
}
}
// This code is contributed by DrRoot_<?php
// PHP code for linearly search x in arr[].
// If x is present then return its location,
// otherwise return -1
function search($arr, $x)
{
$n = sizeof($arr);
for($i = 0; $i < $n; $i++)
{
if($arr[$i] == $x)
return $i;
}
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$x = 10;
// Function call
$result = search($arr, $x);
if($result == -1)
echo "Element is not present in array";
else
echo "Element is present at index " ,
$result;
// This code is contributed
// by jit_t
?><script>
// Javascript code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
function search(arr, n, x)
{
let i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length;
// Function call
let result = search(arr, n, x);
(result == -1)
? document.write("Element is not present in array")
: document.write("Element is present at index " + result);
// This code is contributed by Manoj
</script>Saída
O elemento está presente no índice 3
A complexidade de tempo do algoritmo acima é O (n).
A pesquisa linear raramente é usada de forma prática porque outros algoritmos de pesquisa, como o algoritmo de pesquisa binária e as tabelas de hash, permitem uma comparação de pesquisa significativamente mais rápida com a pesquisa linear.
Melhorar a complexidade de pior caso de pesquisa linear
- se o elemento for encontrado no último O (n) a O (1)
- se o elemento não for encontrado O (n) para O (n / 2)
Abaixo está a implementação:
// C++ program for linear search
#include<bits/stdc++.h>
using namespace std;
void search(vector<int> arr, int search_Element)
{
int left = 0;
int length = arr.size();
int position = -1;
int right = length - 1;
// Run loop from 0 to right
for(left = 0; left <= right;)
{
// If search_element is found with
// left variable
if (arr[left] == search_Element)
{
position = left;
cout << "Element found in Array at "
<< position + 1 << " Position with "
<< left + 1 << " Attempt";
break;
}
// If search_element is found with
// right variable
if (arr[right] == search_Element)
{
position = right;
cout << "Element found in Array at "
<< position + 1 << " Position with "
<< length - right << " Attempt";
break;
}
left++;
right--;
}
// If element not found
if (position == -1)
cout << "Not found in Array with "
<< left << " Attempt";
}
// Driver code
int main()
{
vector<int> arr{ 1, 2, 3, 4, 5 };
int search_element = 5;
// Function call
search(arr, search_element);
}
// This code is contributed by mayanktyagi1709// Java program for linear search
import java.io.*;
class GFG
{
public static void search(int arr[], int search_Element)
{
int left = 0;
int length = arr.length;
int right = length - 1;
int position = -1;
// run loop from 0 to right
for (left = 0; left <= right;)
{
// if search_element is found with left variable
if (arr[left] == search_Element)
{
position = left;
System.out.println(
"Element found in Array at "
+ (position + 1) + " Position with "
+ (left + 1) + " Attempt");
break;
}
// if search_element is found with right variable
if (arr[right] == search_Element)
{
position = right;
System.out.println(
"Element found in Array at "
+ (position + 1) + " Position with "
+ (length - right) + " Attempt");
break;
}
left++;
right--;
}
// if element not found
if (position == -1)
System.out.println("Not found in Array with "
+ left + " Attempt");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int search_element = 5;
// Function call
search(arr,search_element);
}
}# Python3 program for linear search
def search(arr, search_Element):
left = 0
length = len(arr)
position = -1
right = length - 1
# Run loop from 0 to right
for left in range(0, right, 1):
# If search_element is found with
# left variable
if (arr[left] == search_Element):
position = left
print("Element found in Array at ", position +
1, " Position with ", left + 1, " Attempt")
break
# If search_element is found with
# right variable
if (arr[right] == search_Element):
position = right
print("Element found in Array at ", position + 1,
" Position with ", length - right, " Attempt")
break
left += 1
right -= 1
# If element not found
if (position == -1):
print("Not found in Array with ", left, " Attempt")
# Driver code
arr = [1, 2, 3, 4, 5]
search_element = 5
# Function call
search(arr, search_element)
# This code is contributed by Dharanendra L V.// C# program for linear search
using System;
class GFG
{
public static void search(int []arr,
int search_Element)
{
int left = 0;
int length = arr.Length;
int right = length - 1;
int position = -1;
// run loop from 0 to right
for (left = 0; left <= right;)
{
// if search_element is found with left variable
if (arr[left] == search_Element)
{
position = left;
Console.WriteLine(
"Element found in Array at "
+ (position + 1) + " Position with "
+ (left + 1) + " Attempt");
break;
}
// if search_element is found with right variable
if (arr[right] == search_Element)
{
position = right;
Console.WriteLine(
"Element found in Array at "
+ (position + 1) + " Position with "
+ (length - right) + " Attempt");
break;
}
left++;
right--;
}
// if element not found
if (position == -1)
Console.WriteLine("Not found in Array with "
+ left + " Attempt");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int search_element = 5;
// Function call
search(arr,search_element);
}
}
// This code is contributed by 29AjayKumar<script>
// Javascript program for linear search
function search(arr, search_Element)
{
let left = 0;
let length = arr.length;
let right = length - 1;
let position = -1;
// Run loop from 0 to right
for(left = 0; left <= right;)
{
// If search_element is found
// with left variable
if (arr[left] == search_Element)
{
position = left;
document.write(
"Element found in Array at " +
(position + 1) + " Position with " +
(left + 1) + " Attempt");
break;
}
// If search_element is found
// with right variable
if (arr[right] == search_Element)
{
position = right;
document.write(
"Element found in Array at " +
(position + 1) + " Position with " +
(length - right) + " Attempt");
break;
}
left++;
right--;
}
// If element not found
if (position == -1)
document.write("Not found in Array with " +
left + " Attempt");
}
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let search_element = 5;
// Function call
search(arr, search_element);
// This code is contributed by code_hunt
</script>Saída
Elemento encontrado na array na posição 5 com 1 tentativa
<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/4GPdGsB3OSc?feature=oembed" width="665"></iframe>
Veja também - Pesquisa Binária
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
