Binary Search in DSA – Complete Guide

Binary Search is one of the most fundamental and efficient searching algorithms in Data Structures and Algorithms (DSA). It is widely used in real-life systems such as databases, searching in dictionaries, and libraries like bisect in Python or binary_search in C++ STL.

📌 What is Binary Search?

Binary Search is a divide and conquer algorithm used to find the position of a target element in a sorted array.

Instead of scanning each element (like Linear Search), Binary Search divides the array into halves and eliminates one half at each step.

✅ Key Points

• Works only on sorted arrays/lists.
• Time Complexity: O(log n).
• Space Complexity: O(1) (iterative) or O(log n) (recursive due to call stack).
• Faster than Linear Search O(n) when dealing with large datasets.

⚡ Intuition (How to Think?)

Imagine you are searching for a word in a dictionary:

1. You don’t start from the first word.
2. You open the dictionary in the middle.
3. If the word you want comes before the opened word → search in the left half.
4. If it comes after → search in the right half.
5. Repeat until found or not found.

That’s exactly how Binary Search works!

🧮 Algorithm Steps

1. Start with two pointers:
   • low = 0 (start index)
   • high = n-1 (end index)
2. Find the middle index: mid = (low + high) / 2
3. Compare:
   • If arr[mid] == target → element found.
   • If arr[mid] > target → search in the left half (high = mid - 1).
   • If arr[mid] < target → search in the right half (low = mid + 1).
4. Repeat until low <= high.

💻 Iterative Implementation (in PHP)

<?php
function binarySearch($arr, $target) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);

        if ($arr[$mid] == $target) {
            return $mid; // Element found
        } elseif ($arr[$mid] < $target) {
            $low = $mid + 1; // Search right
        } else {
            $high = $mid - 1; // Search left
        }
    }
    return -1; // Element not found
}

// Example usage
$arr = [2, 4, 6, 10, 15, 20, 25];
$target = 15;

$result = binarySearch($arr, $target);
echo ($result != -1) ? "Element found at index $result" : "Element not found";
?>

💻 Recursive Implementation

<?php
function binarySearchRecursive($arr, $low, $high, $target) {
    if ($low > $high) {
        return -1; // Not found
    }

    $mid = intdiv($low + $high, 2);

    if ($arr[$mid] == $target) {
        return $mid;
    } elseif ($arr[$mid] < $target) {
        return binarySearchRecursive($arr, $mid + 1, $high, $target);
    } else {
        return binarySearchRecursive($arr, $low, $mid - 1, $target);
    }
}

// Example usage
$arr = [1, 3, 5, 7, 9, 11];
$target = 7;
$result = binarySearchRecursive($arr, 0, count($arr)-1, $target);
echo ($result != -1) ? "Element found at index $result" : "Element not found";
?>

⏱ Complexity Analysis

1. Best Case: O(1) → when the middle element is the target.
2. Average Case: O(log n).
3. Worst Case: O(log n).

Example: For an array of size n = 1,000,000, Binary Search will take at most log₂(1,000,000) ≈ 20 steps.

📊 Applications of Binary Search

• Searching in sorted arrays.
• Efficiently finding elements in large datasets.
• In libraries like C++ STL (binary_search).
• Problems like:
  • Finding square root of a number.
  • Searching in rotated sorted arrays.
  • Peak element finding.
  • Allocating resources (e.g., minimum number of pages allocation problem).