Algorithmic Steps:

To perform a linear search, we follow these steps:

1. Accept the target element and the collection as inputs.

2. Begin traversing the collection from the first element.

3. Compare each element with the target element.

4. If a match is found, return the index or the element itself.

5. If the entire collection is traversed without finding a match, indicate that the target element is not present.

   Advantages of Linear Search

   1. Simplicity:

      • Easy to understand and implement.

   2. No Sorting Required:

      • Works efficiently on both sorted and unsorted data.

   3. Small Input Sizes:

      • Performs well when the dataset is small.

   4. Versatile:

      • Can handle dynamic data (unsorted or unordered data).

      • Can search within any custom range of elements.

   5. No Additional Memory Needed:

      • Constant space complexity O(1).

Disadvantages of Linear Search

1. Inefficient for Large Datasets:

   • Time complexity of O(n) makes it slow for large arrays when compared to other search algorithms (like binary search with O(log n) for sorted arrays).

2. Poor Performance for Frequent Searches:

   • If the same search operation is required repeatedly, the algorithm lacks efficiency.

3. No Optimizations for Sorted Data:

   • Even if the data is sorted, it doesn't benefit from early stopping like binary search.

4. High Comparisons for Worst Cases:

   • If the element is at the end of the array or absent, all elements need to be checked.

5. Inefficient for Repetitive Lookups:

   • Searching repeatedly in the same data set becomes resource-intensive.

When to Use Linear Search

• When the dataset is small or unsorted.

• When simplicity is more important than performance.

• If the dataset changes frequently, making sorting impractical.

When to Avoid Linear Search

• For large datasets, prefer efficient algorithms like binary search or hash-based searches if sorting is possible.

Time Complexity of Linear Search:

1. Best Case (O(1)):

   • The target element is found at the very first position in the array.

2. Worst Case (O(n)):

   • The target element is found at the last position or is not present in the array at all.

   • The algorithm needs to traverse all n elements in the array.

3. Average Case (O(n)):

   • On average, the target element is found around the middle of the list after examining n/2 elements. However, constant factors are ignored, making it O(n).

Space Complexity:

• O(1): No additional space is used apart from a few variables (target, loop counters).

• No additional data structures are created, hence the space complexity is O(1).

Linear search example

import java.util.Scanner;         //scanner class helps in taking input
public class Linearsearch {
    public static void main(String[] args) {
       //implement linear search u have to find its index
       int []arr = {1,21,654,9,649,86,5,68,9,649,79,4,46,84,68,359,89,68,4}; //declaration and initialization of array
        System.out.println("enter element to find");      
        Scanner sc = new Scanner(System.in); //taking input form system
        int n = sc.nextInt();        //storing input on variable named n
        System.out.println(linearsearch(arr,n)); //calling funcation or method and printing its value
    }
    static int linearsearch(int []array,int target){ //method for linear search passing  an array, target element
        if(array.length==0){    //if length of array is 0 means there is no element in array it is empty
            return -1;    //returning -1 if array is empty
        }
        for(int i=0;i<array.length;i++){ //iterating through all element of array by index i
            int element=array[i]; 
            if(element==target){    //if element is equal to target element then return 1 
                return 1;
            }  
        }  
         return -1; // returning -1 as after iterating though all element of array using for loop  no such element found wehre target qquals to element in array
    }
}

Printing messages if element is not present

import java.util.Scanner;         
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 21, 654, 9, 649, 86, 5, 68, 9, 649, 79, 4, 46, 84, 68, 359, 89, 68, 4};

        System.out.println("Enter element to find:");
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();

        int index = linearSearch(arr, target);

        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not present");
        }

        sc.close();
    }

    static int linearSearch(int[] array, int target) {
        if (array.length == 0) {
            System.out.println("Array is empty");
            return -1;
        }

        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Performing linear search within boundary set by the users

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc= new Scanner(System.in);
        int[] arr = {1, 21, 654, 9, 649, 86, 5, 68, 9, 649, 79, 4, 46, 84, 68, 359, 89, 68, 4};  
        System.out.println("Enter element to search fro array: ");
        int target=sc.nextInt(); 
        System.out.println("Enter position from where search begins: ");
        int start=sc.nextInt();
        System.out.println("Enter position till where the search to performed: ");
        int stop=sc.nextInt();

        int x=linearSearch(arr,start,stop,target);
        if(x==1){
            System.out.println("element found");
        }else{
            System.out.println("not found in given range");
           }
    }
        static int linearSearch(int [] array,int start,int stop,int target){
            if(array.length==0){
                return -1;
                }
            for(int i=start;i<stop;i++){
                if(array[i]==target){
                    return 1;
                }
            }
           return -1;
        }
}