Search Algorithm - Sequential Search And Binary Search

Sequential Search

Definition

Sequential Search, also known as Linear Search, is a straightforward searching algorithm used to find a specific element within a collection of elements, such as an array or a list. It works by examining each element one by one, starting from the beginning, until either the target element is found or the entire collection has been traversed. Sequential Search is easy to understand and implement but has a linear time complexity of O(n) in the worst case, making it less efficient for large datasets compared to more advanced search algorithms like Binary Search for sorted arrays.

Code

public class SeqSearch {
    public static void main(String[] args) {
        // Create an integer array to search within
        int[] arr = {1, 9, 5, 77, 11, 3, 56};

        // Define the target element to search for
        int target = 11;

        // Call the seqSearch function to find the target element in the array
        int index = seqSearch(arr, target);

        // Print the index where the target element was found (or -1 if not found)
        System.out.println(index);
    }

    /**
     * Sequential search algorithm to find the target element in an array.
     *
     * @param arr    The array to search within
     * @param target The element to search for
     * @return The index of the target element if found, or -1 if not found
     */
    public static int seqSearch(int[] arr, int target) {
        // Iterate through the array
        for (int i = 0; i < arr.length; i++) {
            // Check if the current element is equal to the target
            if (arr[i] == target) {
                // Return the index where the target element was found
                return i;
            }
        }

        // If the target element is not found, return -1
        return -1;
    }
}

Binary Search

Definition

Binary Search is a highly efficient search algorithm used to find a specific element within a sorted collection of elements, such as an array. It works by repeatedly dividing the search interval in half and comparing the middle element with the target element. If the middle element matches the target, the search is successful. If the target is smaller, the search continues in the left half of the interval; if it’s larger, the search continues in the right half. Binary Search has a time complexity of O(log n) in the worst case, making it significantly faster than linear search algorithms for large datasets, but it requires that the data be sorted prior to searching.

Code

public class BinarySearch {
    public static void main(String[] args) {
        // Create a sorted integer array to search within
        int[] arr = {0, 1, 2, 3, 5, 8, 9};

        // Call the binarySearch function to search for the target element (4) in the array
        System.out.println(binarySearch(arr, 0, arr.length - 1, 4));
    }

    /**
     * Recursive binary search algorithm to find the target element in a sorted array.
     *
     * @param arr    The sorted array to search within
     * @param left   The left pointer (start index of the search range)
     * @param right  The right pointer (end index of the search range)
     * @param target The element to search for
     * @return The index of the target element if found, or -1 if not found
     */
    public static int binarySearch(int[] arr, int left, int right, int target) {
        // Calculate the middle index and value
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        // Check if the left pointer has crossed the right pointer (base case for termination)
        if (left > right) {
            return -1; // Target element not found
        }

        // Compare the target with the middle value
        if (target > midVal) {
            // If the target is greater, search the right half of the array
            return binarySearch(arr, mid + 1, right, target);
        } else if (target < midVal) {
            // If the target is smaller, search the left half of the array
            return binarySearch(arr, left, mid - 1, target);
        } else {
            // If the target is equal to the middle value, return its index
            return mid;
        }
    }
}