Skip to main content

Linear and Binary Search

Searching algorithms are designed to retrieve an element from any data structure where it is stored.

Linear search is the simplest search algorithm. It traverses the array sequentially until it finds the target element.

  • Time Complexity: O(n) - worst case requires checking every element.
  • Space Complexity: O(1) - requires no extra memory.
  • Use Case: When the array is unsorted and small.

Java Implementation​

public class LinearSearch {
    public static int search(int arr[], int x) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1; // Element not found
    }
}

Binary Search is a much more efficient search algorithm but it requires the array to be sorted. It works by repeatedly dividing the search interval in half.

  • Time Complexity: O(log n) - cuts the search space in half each iteration.
  • Space Complexity: O(1) (Iterative) or O(log n) (Recursive call stack).

Iterative Java Implementation​

public class BinarySearch {
    public static int search(int arr[], int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is present at mid
            if (arr[mid] == target)
                return mid;

            // If target greater, ignore left half
            if (arr[mid] < target)
                left = mid + 1;

            // If target is smaller, ignore right half
            else
                right = mid - 1;
        }

        // Element not present
        return -1;
    }
}