Day 19: Searching Algorithms – Linear and Binary Search

Searching algorithms are essential in computer science, enabling us to find specific elements within data structures efficiently. In this post, we will explore two fundamental searching algorithms: Linear Search and Binary Search. We’ll discuss their explanations, implementations in Java, key differences, and example problems.

What is Linear Search?

Linear Search is the simplest searching algorithm. It works by sequentially checking each element in the array until the desired element is found or the end of the array is reached. This algorithm does not require the array to be sorted.

Implementation in Java

Here’s how you can implement Linear Search in Java:

javaCopy codepublic 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 the index of the found element
            }
        }
        return -1; // Return -1 if the element is not found
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        int target = 4;
        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

What is Binary Search?

Binary Search is a more efficient searching algorithm that requires the array to be sorted. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half; if greater, it continues in the right half.

Implementation in Java

Here’s how you can implement Binary Search in Java:

javaCopy codepublic class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate the middle index

            if (arr[mid] == target) {
                return mid; // Target found
            }
            if (arr[mid] < target) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
        return -1; // Return -1 if the element is not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        int target = 4;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

Key Differences Between Linear Search and Binary Search

Feature	Linear Search	Binary Search
Array Order	Unsorted array	Requires sorted array
Time Complexity	O(n)	O(log n)
Space Complexity	O(1) (iterative version)	O(1) (iterative version)
Use Case	Small datasets or unsorted data	Large sorted datasets

Example Problems

1. Linear Search Example: Given an array of integers: {10, 15, 20, 25, 30} and a target value of 20, Linear Search will return the index 2.
2. Binary Search Example: Given a sorted array: {1, 2, 3, 4, 5} and a target value of 3, Binary Search will return the index 2.

Conclusion

Linear Search and Binary Search are fundamental searching algorithms with distinct use cases. Linear Search is simple and works on unsorted data, while Binary Search is efficient and ideal for sorted datasets. Understanding both algorithms is crucial for effective data retrieval.

In our next post, we will explore Recursion and its importance in algorithms. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB