Array Search Using Binary Search in DSA

🧠 DSA Approach to Think

Whenever you solve Binary Search, think like this:

1. ✅ First, make sure the array is sorted.
2. ✅ Maintain two pointers: low (start index), high (end index).
3. ✅ Loop while low <= high.
4. ✅ Find mid = (low + high) / 2.
5. ✅ Compare:
   • If arr[mid] == target → element found.
   • If arr[mid] > target → move high = mid - 1.
   • If arr[mid] < target → move low = mid + 1.

📝 Binary Search in PHP (Code)

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

    while ($low <= $high) {
        // Find middle index
        $mid = (int)(($low + $high) / 2);

        // Check if target is at mid
        if ($arr[$mid] == $target) {
            return $mid; // element found at index
        }

        // If target is smaller, ignore right half
        if ($arr[$mid] > $target) {
            $high = $mid - 1;
        } 
        // If target is larger, ignore left half
        else {
            $low = $mid + 1;
        }
    }

    return -1; // element not found
}

// Example usage
$arr = [10, 20, 30, 40, 50, 60, 70];
$target = 40;

$result = binarySearch($arr, $target);

if ($result != -1) {
    echo "Element $target found at index: $result";
} else {
    echo "Element $target not found in array.";
}
?>

📊 Output

Element 40 found at index: 3

⏱ Time & Space Complexity

• Time Complexity:
  • Best Case: O(1) (element at mid in first try)
  • Worst Case: O(log n)
• Space Complexity: O(1) (no extra space needed except variables)

🙋 FAQs (Interview-Oriented)

Q1: Can Binary Search work on an unsorted array?
No ❌, array must be sorted.

Q2: What is the difference between iterative and recursive binary search?

• Iterative uses loops.
• Recursive calls itself with reduced range.

Q3: Why Binary Search is faster than Linear Search?
Because it reduces the search space by half at every step.

Q4: What is the limitation of Binary Search?
Array must be sorted before applying Binary Search.