この記事では、線形検索アルゴリズムについて説明します。検索は、リスト内の特定の要素を見つけるプロセスです。要素がリストに存在する場合、プロセスは成功と呼ばれ、プロセスはその要素の場所を返します。それ以外の場合、検索は失敗したと呼ばれます。
よく使用される 2 つの検索方法は、線形検索と二分検索です。そこで、ここでは一般的な検索手法である線形検索アルゴリズムについて説明します。
線形探索は次のように呼ばれます。 逐次検索アルゴリズム。 最も単純な検索アルゴリズムです。線形検索では、単純にリストを完全に横断し、リストの各要素と位置を検索する項目を照合します。一致するものが見つかった場合は、アイテムの場所が返されます。それ以外の場合、アルゴリズムは NULL を返します。
順序なしリスト、つまり項目が並べ替えられていないリストから要素を検索するために広く使用されています。線形探索の最悪の場合の時間計算量は次のとおりです。 の上）。
線形検索の実装で使用される手順は次のとおりです。
- まず、配列要素を走査する必要があります。 のために ループ。
- それぞれの反復で for ループ、 検索要素と現在の配列要素を比較し、そして -
- 要素が一致する場合は、対応する配列要素のインデックスを返します。
- 要素が一致しない場合は、次の要素に移動します。
- 一致するものがない場合、または指定された配列に検索要素が存在しない場合は、戻り値を返します。 -1.
ここで、線形探索のアルゴリズムを見てみましょう。
アルゴリズム
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></=> 出力
プログラム： 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'; ?> 出力
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。