Linear Search Algorithm,Java Program and Complexity


Linear search also called sequential search is a way for finding a target value within a list. It sequentially checks each element from the list for the target value until a match is found or until all the elements have been searched.

Algorithm

  • Target value search start from the leftmost element of array[] and one by one compare target value with each element of array[]
  • If target value matches with an element, return the index.
  • If target value doesn’t match with any of elements, return -1.

Complexity

  • Best Case Performance O(1)
  • Average Case Performance O(n)
  • Worst Case Performance O(1)

Where O is BiG-O Notation and n is no of element in Array/List.

Java Program for Linear Search of Element

import java.util.Scanner;

class LinearSearch {
	public static void main(String args[]) {
		int c, n, targetValue, array[];

		Scanner in = new Scanner(System.in);
		System.out.println("Enter number of elements");
		n = in.nextInt();
		array = new int[n];

		System.out.println("Enter " + n + " integers");

		for (c = 0; c < n; c++)
			array[c] = in.nextInt();

		System.out.println("Enter target value to find");
		targetValue = in.nextInt();

		for (c = 0; c < n; c++) {
			if (array[c] == targetValue)
			{
				System.out.println(targetValue + " is present at location " + (c + 1) + ".");
				break;
			}
		}
		if (c == n)
			System.out.println(targetValue + " is not present in array.");
	}
}

Output

Enter number of elements
10
Enter 10 integers
2
56
3
7
89
34
78
23
67
13
Enter target value to find
7
7 is present at location 4.

Enter number of elements
7
Enter 7 integers
12
45
34
78
23
87
90
Enter target value to find
32
32 is not present in array.

More

For more DataStructure,Algorithms and Java Programing Test questions and sample code follow below links

About Saurabh Gupta

My Name is Saurabh Gupta, I have approx. 10 Year of experience in Information Technology World manly in Java/J2EE. During this time I have worked with multiple organization with different client, so many technology, frameworks etc.
This entry was posted in Algorithm, Data Structure, Programming Test, Search and tagged , , , , , , , , . Bookmark the permalink.