Binary Search

Binary Search is an efficient algorithm for finding a target value within a sorted collection (array or list).

It repeatedly divides the collection in half until the target value is found or the entire collection has been searched.

Binary search is a divide-and-conquer algorithm. In divide-and-conquer algorithms, the problem is divided into smaller subproblems that are easier to solve. These solutions are then combined to solve the original problem.

In the case of binary search, the “divide” step involves halving the portion of the array that could contain the target value. The “conquer” step is identifying which half to continue searching in, based on whether the target value is greater or smaller than the middle element. This process is repeated until the target element is found or the search interval is empty.

Java Implementation

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // Element not found
    }

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

Complexity Analysis

1. Time Complexity: O(logn) – The list is repeatedly halved in search of the target, leading to logarithmic time complexity.
2. Space Complexity: O(1) – Only a constant amount of extra memory is used, regardless of the input size.

Importance of Binary Search

1. Efficiency: It’s much faster than linear search O(n)) when dealing with sorted data.
2. Practicality: Frequently used in practical coding problems and real-world applications.
3. Precondition: The only requirement is that the input data must be sorted.
4. Easy to Implement: Despite its efficiency, the algorithm is straightforward and easy to implement.