In this blog, we are going to learn about implementing the Linear Search Algorithm Data Structures using Java.

Linear Search

• The sequential search (also called the linear search) is the simplest search algorithm.
• It is also the least efficient.
• It simply examines each element sequentially, starting with the first element, until it finds the key element or it reaches the end of the array. Example: If you were looking for someone on a moving passenger train, you would use a sequential search.

Algorithm

A Linear array DATA with N elements and a specific ITEM of information are given. This algorithm finds the location LOC of ITEM in the array DATA or sets LOC = 0.

1. [Initialize] Set K := 1 and LOC := 0.
2. Repeat Steps 3 and 4 while LOC = 0 and K <= N.
3. If ITEM = DATA[K], then: Set LOC := K.
4. Set K := K + 1. [Increments counter.] [End of Step 2 loop.]
5. [Successful?] If Loc = 0, then:
   Write: ITEM is not in the array DATA.
   Else:
   Write: LOC is the location of the ITEM.
   [End of If structure.]
6. Exit.

Performance

• The sequential search runs in O(n) time.
• This means that, on average, the running time is proportional to the number of elements in the array.
• If x is in the sequence, say at x = s • If x is in the sequence, say at x = si with i < n, then i with i < n, then the loop will iterate i times. In that case, the running time is proportional to i, which is O(n) since i < n.
• If x is not in the sequence, then the loop will iterate n times, making the running time proportional to n, which is O(n).

Linear Search in Java

public class BehindJava {

	public static void main(String[] args) {
		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

		System.out.println("Found at Location:"+linearSearch(intArray, -15));
		System.out.println("Found at Location:"+linearSearch(intArray, 1));
		System.out.println("Found at Location:"+linearSearch(intArray, 8888));
		System.out.println("Found at Location:"+linearSearch(intArray, -22));
	}

	public static int linearSearch(int[] input, int value) {
		for (int i = 0; i < input.length; i++) {
			if (input[i] == value) {
				return i;
			}
		}
		return -1;
	}
}

Output:

Found at Location:2
Found at Location:5
Found at Location:-1
Found at Location:6