<p><span style="color: #008000;"><strong>Linear search</strong></span> is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.</p>
<p><img class="alignnone size-full wp-image-67" src="https://c1ctech.com/wp-content/uploads/2018/02/linear_search.png" alt="linear_search" width="507" height="164" /></p>
<p>For example, consider an array of integers of size <span id="MathJax-Element-1-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: 400; line-height: normal; font-size: 14px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: #252c33; font-family: 'Open Sans', sans-serif; font-variant-ligatures: normal; font-variant-caps: normal; orphans: 2; widows: 2; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; position: relative;" tabindex="0" role="presentation" data-mathml="<;math xmlns=";http://www.w3.org/1998/Math/MathML";>;<;mi>;N<;/mi>;<;/math>;"><span class="MJX_Assistive_MathML" role="presentation">N</span></span>. You should find and print the position of all the elements with value <span id="MathJax-Element-2-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: 400; line-height: normal; font-size: 14px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: #252c33; font-family: 'Open Sans', sans-serif; font-variant-ligatures: normal; font-variant-caps: normal; orphans: 2; widows: 2; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; position: relative;" tabindex="0" role="presentation" data-mathml="<;math xmlns=";http://www.w3.org/1998/Math/MathML";>;<;mi>;x<;/mi>;<;/math>;"><span class="MJX_Assistive_MathML" role="presentation">x</span></span>. Here, the linear search is based on the idea of matching each element from the beginning of the list to the end of the list with the integer <span id="MathJax-Element-3-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; font-weight: 400; line-height: normal; font-size: 14px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: #252c33; font-family: 'Open Sans', sans-serif; font-variant-ligatures: normal; font-variant-caps: normal; orphans: 2; widows: 2; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; position: relative;" tabindex="0" role="presentation" data-mathml="<;math xmlns=";http://www.w3.org/1998/Math/MathML";>;<;mi>;x<;/mi>;<;/math>;"><span class="MJX_Assistive_MathML" role="presentation">x</span></span>, and then printing the position of the element if the condition is `True&#8217;.</p>
<!-- WP QUADS Content Ad Plugin v. 2.0.98.1 -->
<div class="quads-location quads-ad2" id="quads-ad2" style="float:none;margin:0px;">

</div>

<h4><span style="color: #000080;"><strong>Algorithm:</strong></span></h4>
<ul class="points">
<li><span style="color: #0000ff;"><strong>Step 1:</strong></span> Traverse the array</li>
<li><strong><span style="color: #0000ff;">Step 2:</span></strong> Match the key element with array element</li>
<li><span style="color: #0000ff;"><strong>Step 3:</strong></span> If key element is found, return the index position of the array element</li>
<li><span style="color: #0000ff;"><strong>Step 4:</strong></span> If key element is not found, return -1</li>
</ul>
<p>Let&#8217;s see an example of linear search in java where we are going to search an element sequentially from an array.</p>
<pre style="padding-left: 30px;"><strong><code><span style="color: #0000ff;">//Java code for linearly search an item in an arr[].</span>
<span style="color: #0000ff;">//If item is present then it will return its index and location </span>
<span style="color: #0000ff;">//otherwise return -1
</span>public class Search {

<span style="color: #0000ff;">//this function returns index of element <span style="color: #008000;">itemToSearch</span> in arr[]</span>
public int linearSearch(int arr[], int n, int item) 
{
 for (int i = 0; i <;= n; i++) 
 {
<span style="color: #0000ff;"> //return the index of the element if it is found
</span> if (item == arr[i])
 return i;
 }
<span style="color: #0000ff;"> //return -1 if the element is not found
</span> return -1;
}

public static void main(String[] strr) {
int noOfItem, itemToSearch;
int arr[] = {7, 9, 12, 24, 13, 67};
noOfItem = arr.length - 1;
itemToSearch = 13;
int index = new Search().linearSearch(arr, noOfItem, itemToSearch);
if (index==-1)
System.out.println("item does not exist");
else
System.out.println("Item"+" " +itemToSearch+" " + "found at index :" + index + " and " +"position :" + (index+1));
}

}</code></strong></pre>
<h4><span style="color: #000080;"><strong>Output:</strong></span></h4>
<p><span style="color: #0000ff;"><strong>Item 13 found at index :4 and position :5</strong></span></p>
<h4><span style="color: #000080;"><strong>Time Complexity:</strong></span></h4>
<p>The time complexity of the linear search is <strong><span id="MathJax-Element-9-Frame" class="MathJax_SVG" style="display: inline-block; font-style: normal; line-height: normal; font-size: 14px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; color: #008000;" tabindex="0" role="presentation" data-mathml="<;math xmlns=";http://www.w3.org/1998/Math/MathML";>;<;mi>;O<;/mi>;<;mo stretchy=";false";>;(<;/mo>;<;mi>;N<;/mi>;<;mo stretchy=";false";>;)<;/mo>;<;/math>;"><span class="MJX_Assistive_MathML" role="presentation">O(N)</span></span></strong> because each element in an array is compared only once.</p>
<p>Linear search is rarely used practically because other search algorithms such as the <span style="color: #008000;"><strong>binary search</strong></span> algorithm and <span style="color: #008000;"><strong>hash tables</strong></span> allow significantly faster searching comparison to Linear search.</p>
<p> ;</p>