Sequential Search in Java

Filed Under: Java
Sequential Search

A sequential search is a straight forward way to look for an element in a collection. This type of search uses a loop to go over each element one by one and see if it matches with the element we are looking for. The searching mechanism moves in a sequence, hence the name Sequential search.

In case the data is sorted, we can reduce the number of lookups. We can stop the search when we exceed the target element. This is only possible in the case when the target element is not present.

Simple Sequential Search

In the case of unsorted data, the search method goes over all the elements. At each position, it compares the element at that position to the one we are looking for. If we find a match, we return true otherwise we continue our search. If we reach the end and no match is found, we return false.

package com.journaldev.java;

import java.util.ArrayList;
import java.util.Arrays;
public class Main {

    public static void main(String[] args) {
        int[] a = {3,2,4,5,3,2,7,6,4};
        boolean ans = contains(a,7);
        if(ans) {
            System.out.println("Number found");
        }
        else{
            System.out.println("Number not found");
        }

    }
    public static boolean contains(int[] a, int b){
        for (int i : a) {
            if (i==b){
                return true;
            }
        }
        return false;
    }
}
Number Found

Sequential Search in Sorted Array

Sequential search over sorted data doesn’t always reduce the complexity or the number of lookups we need to perform. However in case, the element is not present, then we can stop our search the moment our search exceeds the target element.

package com.journaldev.java;

import java.util.ArrayList;
import java.util.Arrays;
public class Main {

    public static void main(String[] args) {
        int[] a = {1,2,3,4,6,7,9};
        boolean ans = contains(a,5);
        if(ans) {
            System.out.println("Number found");
        }
        else{
            System.out.println("Number not found");
        }

    }
    public static boolean contains(int[] a, int b){
        for (int i : a) {
            System.out.println("Comparing with :" +i);
            if (i==b){
                return true;
            }
            else if(i>b){
                return false;
            }
        }
        return false;
    }
}
Sequential Search in sorted data

In this code, we print the number our search mechanism is comparing with. We can see that the search stops at 6 since 6 is already greater than 5 and if we move beyond 6 we will only come across numbers greater than 6.

An important thing to note over here is that the worst-case complexity still remains O(n). Since in the worst case, the element we are looking for could be the last element and we would need to go through the entire array.

Conclusion

A sequential search is the most basic search mechanism for searching in arrays. Apart from arrays, it is also common to use a sequential search for searching elements in the Linked List. The worst-case complexity of Sequential search is O(n) where n is the total number of elements.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages