Neste artigo, discutiremos o algoritmo de pesquisa linear. Pesquisar é o processo de encontrar algum elemento específico na lista. Se o elemento estiver presente na lista, o processo será considerado bem-sucedido e retornará a localização desse elemento; caso contrário, a pesquisa será considerada malsucedida.
Dois métodos de pesquisa populares são Pesquisa Linear e Pesquisa Binária. Portanto, discutiremos aqui a técnica de pesquisa popular, ou seja, Algoritmo de Pesquisa Linear.
java concatenar strings
A pesquisa linear também é chamada de algoritmo de pesquisa sequencial. É o algoritmo de pesquisa mais simples. Na pesquisa linear, simplesmente percorremos a lista completamente e combinamos cada elemento da lista com o item cuja localização deve ser encontrada. Se a correspondência for encontrada, a localização do item será retornada; caso contrário, o algoritmo retornará NULL.
É amplamente utilizado para pesquisar um elemento da lista não ordenada, ou seja, a lista na qual os itens não estão ordenados. A complexidade de tempo do pior caso da pesquisa linear é Sobre).
lista de classificação java
As etapas usadas na implementação da Pesquisa Linear estão listadas a seguir -
- Primeiro, temos que percorrer os elementos do array usando um para laço.
- Em cada iteração de para laço, compare o elemento de pesquisa com o elemento da matriz atual e -
- Se o elemento corresponder, retorne o índice do elemento da matriz correspondente.
- Se o elemento não corresponder, passe para o próximo elemento.
- Se não houver correspondência ou o elemento de pesquisa não estiver presente no array fornecido, retorne -1.
Agora, vamos ver o algoritmo de busca linear.
Algoritmo
Linear_Search(a, n, val) // 'a' is the given array, 'n' is the size of given array, 'val' is the value to search Step 1: set pos = -1 Step 2: set i = 1 Step 3: repeat step 4 while i <= 1 6 n step 4: if a[i]="=" val set pos="i" print go to [end of if] i="i" + loop] 5: 'value is not present in the array ' 6: exit < pre> <h2>Working of Linear search</h2> <p>Now, let's see the working of the linear search Algorithm.</p> <p>To understand the working of linear search algorithm, let's take an unsorted array. It will be easy to understand the working of linear search with an example.</p> <p>Let the elements of array are -</p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm.webp" alt="Linear Search Algorithm"> <p>Let the element to be searched is <strong>K = 41</strong> </p> <p>Now, start from the first element and compare <strong>K</strong> with each element of the array.</p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-2.webp" alt="Linear Search Algorithm"> <p>The value of <strong>K,</strong> i.e., <strong>41,</strong> is not matched with the first element of the array. So, move to the next element. And follow the same process until the respective element is found.</p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-3.webp" alt="Linear Search Algorithm"> <p>Now, the element to be searched is found. So algorithm will return the index of the element matched.</p> <h2>Linear Search complexity</h2> <p>Now, let's see the time complexity of linear search in the best case, average case, and worst case. We will also see the space complexity of linear search.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Case</th> <th>Time Complexity</th> </tr> <tr> <td> <strong>Best Case</strong> </td> <td>O(1)</td> </tr> <tr> <td> <strong>Average Case</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Worst Case</strong> </td> <td>O(n)</td> </tr> </table> <ul> <tr><td>Best Case Complexity -</td> In Linear search, best case occurs when the element we are finding is at the first position of the array. The best-case time complexity of linear search is <strong>O(1).</strong> </tr><tr><td>Average Case Complexity -</td> The average case time complexity of linear search is <strong>O(n).</strong> </tr><tr><td>Worst Case Complexity -</td> In Linear search, the worst case occurs when the element we are looking is present at the end of the array. The worst-case in linear search could be when the target element is not present in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is <strong>O(n).</strong> </tr></ul> <p>The time complexity of linear search is <strong>O(n)</strong> because every element in the array is compared only once.</p> <h3>2. Space Complexity</h3> <table class="table"> <tr> <td> <strong>Space Complexity</strong> </td> <td>O(1)</td> </tr> </table> <ul> <li>The space complexity of linear search is O(1).</li> </ul> <h2>Implementation of Linear Search</h2> <p>Now, let's see the programs of linear search in different programming languages.</p> <p> <strong>Program:</strong> Write a program to implement linear search in C language.</p> <pre> #include int linearSearch(int a[], int n, int val) { // Going through array sequencially for (int i = 0; i <n; i++) { if (a[i]="=" val) return i+1; } -1; int main() a[]="{70," 40, 30, 11, 57, 41, 25, 14, 52}; given array val="41;" value to be searched n="sizeof(a)" sizeof(a[0]); size of res="linearSearch(a," n, val); store result printf('the elements the are - '); for (int i="0;" < n; printf('%d ', a[i]); printf('
element is %d', (res="=" -1) not present in array'); else at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-4.webp" alt="Linear Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement linear search in C++.</p> <pre> #include using namespace std; int linearSearch(int a[], int n, int val) { // Going through array linearly for (int i = 0; i <n; i++) { if (a[i]="=" val) return i+1; } -1; int main() a[]="{69," 39, 29, 10, 56, 40, 24, 13, 51}; given array val="56;" value to be searched n="sizeof(a)" sizeof(a[0]); size of res="linearSearch(a," n, val); store result cout<<'the elements the are - '; for (int i="0;" < n; cout< <a[i]<<' cout<<'
element is '<<val; (res="=" -1) not present in array'; else at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-5.webp" alt="Linear Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement linear search in C#.</p> <pre> using System; class LinearSearch { static int linearSearch(int[] a, int n, int val) { // Going through array sequencially for (int i = 0; i <n; i++) { if (a[i]="=" val) return i+1; } -1; static void main() int[] a="{56," 30, 20, 41, 67, 31, 22, 14, 52}; given array int val="14;" value to be searched n="a.Length;" size of res="linearSearch(a," n, val); store result console.write('the elements the are - '); for (int i="0;" < n; console.write(' ' + a[i]); console.writeline(); console.writeline('element is (res="=" -1) not present in array'); else console.write('element at +' position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-6.webp" alt="Linear Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement linear search in Java.</p> <pre> class LinearSearch { static int linearSearch(int a[], int n, int val) { // Going through array sequencially for (int i = 0; i <n; i++) { if (a[i]="=" val) return i+1; } -1; public static void main(string args[]) int a[]="{55," 29, 10, 40, 57, 41, 20, 24, 45}; given array val="10;" value to be searched n="a.length;" size of res="linearSearch(a," n, val); store result system.out.println(); system.out.print('the elements the are - '); for (int i="0;" < n; system.out.print(' ' + a[i]); system.out.println('element is (res="=" -1) not present in array'); else at +' position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-7.webp" alt="Linear Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement linear search in JavaScript.</p> <pre> var a = [54, 26, 9, 80, 47, 71, 10, 24, 45]; // given array var val = 71; // value to be searched var n = a.length; // size of array function linearSearch(a, n, val) { // Going through array sequencially for (var i = 0; i <n; i++) { if (a[i]="=" val) return i+1; } -1 var res="linearSearch(a," n, val); store result document.write('the elements of the array are: '); for (i="0;" i < n; document.write(' ' + a[i]); <br>' + 'Element to be searched is: ' + val); if (res == -1) document.write(' <br>' + 'Element is not present in the array'); else document.write(' <br>' + 'Element is present at ' + res +' position of array'); </n;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-8.webp" alt="Linear Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement linear search in PHP.</p> <pre> <?php $a = array(45, 24, 8, 80, 62, 71, 10, 23, 43); // given array $val = 62; // value to be searched $n = sizeof($a); //size of array function linearSearch($a, $n, $val) { // Going through array sequencially for ($i = 0; $i < $n; $i++) { if ($a[$i] == $val) return $i+1; } return -1; } $res = linearSearch($a, $n, $val); // Store result echo 'The elements of the array are: '; for ($i = 0; $i < $n; $i++) echo ' ' , $a[$i]; echo ' <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/linear-search-algorithm-9.webp" alt="Linear Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;></pre></=> Saída
Programa: Escreva um programa para implementar pesquisa linear em PHP.
<?php $a = array(45, 24, 8, 80, 62, 71, 10, 23, 43); // given array $val = 62; // value to be searched $n = sizeof($a); //size of array function linearSearch($a, $n, $val) { // Going through array sequencially for ($i = 0; $i < $n; $i++) { if ($a[$i] == $val) return $i+1; } return -1; } $res = linearSearch($a, $n, $val); // Store result echo \\'The elements of the array are: \\'; for ($i = 0; $i < $n; $i++) echo \\' \\' , $a[$i]; echo \\' <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> Saída
formato de data.formato
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.