Linear Search vs Binary Search

Linear Search

Linear search is a straightforward search algorithm that looks for a specific element in a list or array.

Example:

Let’s say we have an array arr = [4, 2, 7, 1, 9, 5, 8] and we want to search for the target element 5.

1. Iteration 1: Check if arr[0] (4) is equal to the target (5). No match.
2. Iteration 2: Check if arr[1] (2) is equal to the target (5). No match.
3. Iteration 3: Check if arr[2] (7) is equal to the target (5). No match.
4. Iteration 4: Check if arr[3] (1) is equal to the target (5). No match.
5. Iteration 5: Check if arr[4] (9) is equal to the target (5). No match.
6. Iteration 6: Check if arr[5] (5) is equal to the target (5). Match found! Return index 5.

The linear search algorithm stops once it finds the target element or searches the entire array without finding a match.

Binary Search

Binary search is a more efficient search algorithm, especially for sorted lists or arrays. It works by repeatedly dividing the search interval in half.

Example:

Let’s say we have a sorted array arr = [1, 2, 4, 5, 7, 8, 9] and we want to search for the target element 5.

1. Initial left = 0, right = 6, mid = 3. Element at mid (5) is equal to the target. Return index 3.

The binary search algorithm is more efficient than linear search, especially for large datasets, as it eliminates half of the remaining elements in each iteration.

Complexity Comparision

Linear Search:

• Time Complexity (Big O notation): O(n)

In the worst-case scenario, a linear search may need to iterate through the entire list or array. Therefore, the time complexity is linear, denoted as O(n), where n is the size of the input

• Space Complexity: O(1)

Linear search typically uses a constant amount of additional space. It doesn’t require additional memory proportional to the size of the input.

Binary Search:

• Time Complexity (Big O notation): O(log n)

Binary search reduces the search space by half in each iteration. In the worst-case scenario, it takes log base 2 of n iterations to find the element, where n is the size of the input. Therefore, the time complexity is logarithmic, denoted as O(log n).

• Space Complexity: O(1)

Binary search usually operates in place and doesn’t require additional memory proportional to the size of the input. Its space complexity is constant, denoted as O(1).

In terms of time complexity, binary search is significantly more efficient than linear search for large datasets, especially when the data is sorted. However, it’s important to note that binary search is only applicable to sorted lists or arrays, while linear search can be used on both sorted and unsorted data. The choice between them depends on the characteristics of the data and the specific requirements of the problem at hand.

Example Java Codes For Linear and Binary Search

Example 1

package complexity;

public class LinearSearchExample {

    public static int linearSearch(int[] array, int target) {
        // Iterate through the array
        for (int i = 0; i < array.length; i++) {
            // If the current element is equal to the target, return the index
            if (array[i] == target) {
                return i;
            }
        }
        // If the target is not found, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Example array
        int[] numbers = { 4, 2, 7, 1, 9, 5, 8 };

        // Element to search for
        int target = 5;

        // Perform linear search
        int result = linearSearch(numbers, target);

        // Display the result
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
    }
}

Example 2

package complexity;

public class BinarySearchExample {

    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if the target is present at the middle
            if (array[mid] == target) {
                return mid;
            }

            // If the target is greater, ignore the left half
            if (array[mid] < target) {
                left = mid + 1;
            }
            // If the target is smaller, ignore the right half
            else {
                right = mid - 1;
            }
        }

        // If the target is not present in the array
        return -1;
    }

    public static void main(String[] args) {
        // Example sorted array
        int[] numbers = { 1, 2, 4, 5, 7, 8, 9 };

        // Element to search for
        int target = 5;

        // Perform binary search
        int result = binarySearch(numbers, target);

        // Display the result
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
    }
}

Example 3

public class Demo {
    public static void main(String[] args) {
        int num[] = {1, 2, 3, 5, 7, 9, 11, 13};
        int target = 11;

        //Linear search
        int result1 = linearSearch(num, target);
        if (result1 != -1)
            System.out.println("LinearSearch-Element found of Index : " + result1);
        else
            System.out.println("LinearSearch-Element not found");
        System.out.println("------------------------------------------");
        //Binary Search
        int result2 = binarySearch(num, target);
        if (result2 != -1)
            System.out.println("BinarySearch-Element found of Index : " + result1);
        else
            System.out.println("BinarySearch-Element not found");

    }

    public static int linearSearch(int[] num, int target) {
        int steps = 0;
        for (int i = 0; i < num.length; i++) {
            steps++;
            if (num[i] == target) {
                System.out.println("steps taken by LinearSearch = " + steps);
                return i;
            }
        }
        System.out.println("steps taken by LinearSearch = " + steps);
        return -1;
    }

    public static int binarySearch(int[] num, int target) {
        int steps = 0;
        //5,7,9,11,13
        int left = 0;
        int right = num.length - 1;
        while (left <= right) {
            steps++;
            int mid = (left + right) / 2;
            if (num[mid] == target) {
                System.out.println("steps taken by BinarySearch = " + steps);
                return mid;
            } else if (num[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println("steps taken by BinarySearch = " + steps);
        return -1;
    }

//end Demo class
}