Back to: Java Tutorials

#### Explanation of Linear Search

Linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached.

To understand linear search, consider the following list of numbers: [5, 3, 8, 4, 2]. Suppose we want to find the position of the element 8 in the list. The linear search algorithm starts at the beginning of the list and compares each element with the target element until a match is found.

The figure below shows the linear search algorithm for finding the element 8 in the list [5, 3, 8, 4, 2]:

```
Index 0: 5 -> 8 not found yet
Index 1: 3 -> 8 not found yet
Index 2: 8 -> 8 found at index 2
```

As we can see from the figure, the linear search algorithm compares each element in the list with the target element until it finds a match at index 2, where the element 8 is located.

If the target element is not present in the list, the linear search algorithm will iterate over all the elements in the list and return a “not found” result. The figure below shows the linear search algorithm for finding the element 7 in the list [5, 3, 8, 4, 2]:

```
Index 0: 5 -> 7 not found yet
Index 1: 3 -> 7 not found yet
Index 2: 8 -> 7 not found yet
Index 3: 4 -> 7 not found yet
Index 4: 2 -> 7 not found yet
Not found
```

Another example:

The following figure illustrates the process of linear search for finding the number 7 in the list [5, 9, 3, 7, 1, 8]:

```
[5, 9, 3, 7, 1, 8]
^ (compare 5 with 7, no match)
^ (compare 9 with 7, no match)
^ (compare 3 with 7, no match)
^ (compare 7 with 7, match found)
```

As can be seen from the figure, linear search requires iterating through each element in the list, which can be time-consuming for very large lists. However, for small lists or lists that are not sorted, linear search can be a good option.

In summary, linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached. Linear search is easy to implement, but it can be slow for large lists as it has a time complexity of O(n), where n is the number of elements in the list.

#### Java Code Example on Linear Search

Here is an example of a linear search implementation in Java:

```
public class LinearSearch {
public static int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Target found at index i
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
int target = 8;
int index = search(arr, target);
if (index != -1) {
System.out.println("Target found at index " + index);
} else {
System.out.println("Target not found");
}
}
}
```

In this implementation, the `search`

method takes an array of integers `arr`

and a target integer `target`

, and returns the index of the target in the array if found, or -1 if not found. The `search`

method iterates over each element in the array using a for loop, and checks if the current element is equal to the target. If the target is found, the method returns the index of the current element, which is the index of the target in the array. If the loop finishes without finding the target, the method returns -1 to indicate that the target was not found.

In the `main`

method, we create an example array `arr`

and set the target integer to 8. We then call the `search`

method with `arr`

and `target`

, and store the result in the `index`

variable. We then check if the `index`

is -1 or not, and print the appropriate message to the console.

Note that linear search has a time complexity of O(n), where n is the number of elements in the array, so it is not the most efficient algorithm for large arrays. However, it is a simple algorithm to understand and implement.

Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.

Follow us on social media

Follow Author