Java - Linear Search Algorithm

Linear Search

Linear search in a sequential search algorithm to search a particular element from a given list of elements. It starts from the first element in the list and check each element in sequence till the required element found or list ends. Linear search do not required the list or array to be in sorted order. 

Pseudocode -

# Input: Array elements, integer keyToSearch
# Output: first index of keyToSearch in elements, or -1 if not found
 For i = 0 to last index of elements:
   if elemnts[i] equals keyToSearch:
     return i

 return -1

Asymptotic Analysis of Linear Search Algorithm -

Best Case Scenario - Best case in linear search if the required element is found in first place. Best case time complexity is O(1).

Worst Case Scenario - Worst case in linear search if the element if last element in the list or element is not present in list. Worst case time complexity is O(N).

Complexity - Complexity of linear search algorithm is O(N). The time taken by algorithm to search an element will increase linearly with the number of elements in the list.

Linear Search Implementation in Java  -

package javaprinciples.dsa;

public class LinearSearch {

public static void main(String[] args) {

int[] elements = { 22, 45, 12, 32, 78, 56, 88 };

int keyToSearch = 12;

int keyFoundAt = linerSearch(elements, keyToSearch);

if (keyFoundAt == -1) {

System.out.println("Key " + keyToSearch + " not found in list.");

} else {

System.out.println("Key " + keyToSearch + " found at index: " + keyFoundAt);

}

}

public static int linerSearch(int[] elements, int keyToSearch) {

int size = elements.length;

for (int i = 0; i < size; i++) {

if (elements[i] == keyToSearch) {

return i;

}

}

return -1;

}

}

Output -

Key 12 found at index: 2

So this is all about linear search algorithm and its implementation in Java. I hope you will like it.