What is Binary Search Algorithm and How It Works with Examples.

🔍 Introduction to Binary Search

Binary Search is an efficient searching algorithm used to find the position of a target element within a sorted array or list. Unlike linear search, which checks every element, binary search repeatedly divides the search space in half, drastically reducing the number of comparisons.

📜 How Binary Search Works

• Precondition: The data must be sorted (ascending or descending).
• Identify bounds: Set two pointers, low (start) and high (end).
• Calculate middle: Find the middle index using mid = (low + high) / 2.
• Compare target with middle element:
  • If target equals middle element → target found.
  • If target is smaller → search in the left half.
  • If target is larger → search in the right half.

• Repeat: Continue halving until the target is found or the search space becomes empty.

🐌 Iterative Binary Search

In the iterative approach, we use a loop to adjust search bounds.

public int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Time Complexity: O(log n)
Space Complexity: O(1)

🔄 Recursive Binary Search

The recursive approach breaks down the problem into smaller subproblems.

public int binarySearchRecursive(int[] arr, int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearchRecursive(arr, low, mid - 1, target);
    return binarySearchRecursive(arr, mid + 1, high, target);
}

Time Complexity: O(log n)
Space Complexity: O(log n) – due to recursion stack.

🧠 Key Benefits of Binary Search

• Efficiency: Works in logarithmic time.
• Scalability: Ideal for large datasets.
• Simplicity in Logic: Easy to implement once the concept is clear.

✅ Conclusion

Binary Search is one of the most fundamental algorithms in computer science, widely used in databases, libraries, search engines, and system-level programming. Mastering it not only improves coding skills but also strengthens your understanding of algorithm optimization. Once comfortable, you can explore variations like binary search on rotated arrays or finding boundaries for advanced problem-solving.