###### Linear or Sequential Search Algorithm

Linear or sequential search algorithm is a method for finding a target value within a list.

It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

For a list with n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed.

The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

###### Performance

- Worst-case performance :- O(n)
- Best-case performance :- O(1)
- Average performance :- O(n)
- Worst-case space complexity :- O(1) iterative

###### Java Program of Linear Search Algorithm

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
package com.codenuclear; public class LinearSearch { public static int linearSearch(int[] inputArray,int key) { for(int i=0;i<inputArray.length;i++) { if(inputArray[i] == key) { return i; } } return -1; } public static void main(String args[]) { int[] arr1 = {5,9,10,2,90,4}; int key = 2; int result = linearSearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); //try with another key key = 18; result = linearSearch(arr1,key); System.out.println( (result != -1) ? "Required key:- "+key+" found at index:- "+result : "Key "+key+ " not found"); } } |

Output

Also Read Binary Search Algorithm

Some theory part of this article uses material from the Wikipedia article “Linear search”, which is released under the CC BY-SA 3.0.