Linear Search Algorithm in Java.

Given an integer array of size n and a target element X, the task is to write a Java program to search and return the index of the target element from the given array. Return -1 if the target element is not present in the given array.

Example:

Input: arr[] = {9, 1, 3, 5, 7}  X = 3
Output: Element found at index 2

Input: arr[] = {1, 2, 3, 4, 5, 7, 9}  X = 6
Output: Element not found in the array

This problem can be easily solved by using any search algorithm. In Java, we have two searching algorithms Linear Search and Binary Search, and in this article, we will understand the workings of Linear Search Algorithm and how to use it to find a target element in the given array.

Linear Search Algorithm.

Linear search is a simple searching algorithm that finds the position of a target value within a list. It sequentially checks each element of the list until a match is found or the entire list has been searched.

Step-by-step Algorithm:

Step 1: Start from the first element of the array.

Step 2: Compare the target value with the current element:

If it matches, return the index.
If it doesn't match, move to the next element.

Step 3: Repeat step 2 until a match is found or the end of the array is reached.

Step 4: If the end of the array is reached and no match is found, return -1 to indicate that the element is not present in the array.

Pseudo Code for Linear Search Algorithm.

function linearSearch(arr, target):
    for i from 0 to length of arr - 1:
        if arr[i] equals target:
            return i
    return -1

Java Program for Linear Search Algorithm.

// Java code for linear search algorithm to find and
// return the index of searching element
public class LinearSearch {

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

    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 1, 9, 5};
        int target = 7;

        int result = linearSearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

Output:

Element found at index 2

Time Complexity: In the worst case, linear search has a time complexity of O(n), where n is the number of elements in the array. This is because, in the worst scenario, we may have to go through the entire array to find the element.

Space Complexity: Linear search has a constant space complexity of O(1). It doesn't require additional memory that scales with the size of the input.

Linear search is straightforward and effective for small datasets or unordered lists. However, for large datasets or lists where the elements are sorted, more efficient algorithms like binary search are preferred.

Linear Search Algorithm in Java.

Linear Search Algorithm.

Pseudo Code for Linear Search Algorithm.

Java Program for Linear Search Algorithm.

No comments:

Post a Comment