I den här artikeln kommer vi att diskutera den linjära sökalgoritmen. Att söka är processen att hitta ett visst element i listan. Om elementet finns i listan kallas processen framgångsrik, och processen returnerar platsen för det elementet; annars kallas sökningen misslyckad.
Två populära sökmetoder är linjär sökning och binär sökning. Så här kommer vi att diskutera den populära söktekniken, dvs linjär sökalgoritm.
np var
Linjär sökning kallas också som sekvensiell sökalgoritm. Det är den enklaste sökalgoritmen. I linjär sökning går vi helt enkelt igenom listan helt och hållet och matchar varje element i listan med objektet vars plats ska hittas. Om matchningen hittas returneras varans plats; annars returnerar algoritmen NULL.
Det används ofta för att söka efter ett element från den oordnade listan, det vill säga listan där objekt inte sorteras. Det värsta tänkbara tidskomplexiteten för linjär sökning är På).
Stegen som används i implementeringen av linjär sökning listas enligt följande -
- Först måste vi korsa arrayelementen med hjälp av a för slinga.
- I varje iteration av för slinga, jämför sökelementet med det aktuella arrayelementet, och -
- Om elementet matchar, returnera sedan indexet för motsvarande arrayelement.
- Om elementet inte matchar, gå till nästa element.
- Om det inte finns någon matchning eller sökelementet inte finns i den givna arrayen, returnera -1.
Låt oss nu se algoritmen för linjär sökning.
Algoritm
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></=> Produktion
Program: Skriv ett program för att implementera linjär sökning i 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'; ?> Produktion
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.
strängfunktioner java