Linear Search in Java

0
92
linear search in java
Advertisement

Linear Search in Java is a very simple search algorithm. Linear search or Sequential Search is the method of finding an element in list/array. It can be done by visiting each and every element one by one sequentially. And check if the number is equal to the key(searching element). there are two cases comes :

      1. If the number is equal to the key then return the “index position of the Array”.
      2. If the number is not found then print “Element not found in the given array“.
  • A linear/Sequential search can run its worst-case time complexity of O(N)means while searching the elements in array/list we able to find the element in the last. where linear search needs to compare all the n elements.
  • Linear search best case time complexity is  O(1) means when we start searching the element and elements found in the first place.

Algorithm for Linear Search:

Linear Search (Array A, Value key):

step 1: initialize the iterator variable i=1
step 2:check while i<array.length 
step 3: check if A[i] == key then go to step 6
step 4: else increase iterator variable
step 5: go to step 2
step 6: print the element with the index position
step 7: print element not found
step 8: exit

Linear Search Complexity:

Best Case:  O(1)

Worst case:  O(N)

Pseudo Code:

procedure linearSearch(array,key): 
    for each_item in list: 
        if item == key: 
            return index location 
        end if 
     end for  
end procedure

Linear Search in Java for One dimension Array:

import java.util.Scanner;

public class LinearSearch {

    public static int linearSearch(int arr[], int key) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == key) {
                return (i + 1);
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the Array Size : ");

        int n = sc.nextInt();
        int arr[] = new int[n];
        
        System.out.println("Enter the Array Elements : ");

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("Enter the key to search in the Array : ");

        int key = sc.nextInt();
        int val = linearSearch(arr, key);

        if (val > 0) {
            System.out.println("Element found at position " + val);
        } else {
            System.out.println("Element not found in this Array.");
        }
    }
}
Explanation: Linear search in Java Code
  • As discussed in the above program,  if we assume the example in our post image then:
  • the user enter the size of array and then the elements in the array

Array size : 10

Array elements : [11,12,13,14,15,16,17,18,19,20]

  • then after entering the elements we need to enter the key we want to find in the array :

key : 14

  • After entering the key, program executes the LinearSearch method and compare if key is matched with elements in the array or not.
  • Linear Search process given here while executing the for loop below:
    1.  Key 14 compared with the first element of the array that is 11 but element not matched.
    2. The second element in the array compared to key 14 but element not matched.
    3. Third element on the array compared with key 14 but element not matched.
    4. Fourth array element with index position 3, this time the key 14 matched with the array element.
  • At the end LinearSearch method return the index position of the found element.

In some cases the element not available in the given array then the method LinearSearch returns the negative value that indicates “Element not found” in the given array.

If you find something incorrect in this post please feel free to comment below, or you want to discuss more about the topic then comment feel free to comment.

 

Find below links useful:

Arrays in Java

Array length in Java

Memory Management in Java

LEAVE A REPLY

Please enter your comment!
Please enter your name here