Day 7 — Binary Search in JavaScript

Welcome back to Day 7 of the DSA Master Course 2025!
Today, we’re diving into Binary Search, one of the most efficient and elegant search algorithms you’ll ever meet.

---

What is Binary Search?

Binary Search is an algorithm used to find the position of a target value within a sorted array.
Instead of checking each element one by one like Linear Search, Binary Search divides the search space in half each time until it finds the target (or confirms it’s not there).

Think of it like looking for a word in a dictionary — you don’t start from the first page; you open in the middle, check if you need to go forward or backward, and repeat.

---

How Binary Search Works — Step-by-Step

1. Start with two pointers — one at the start and one at the end of the array.

2. Find the middle element.

3. If the middle element is the target → return its index.

4. If the target is less than the middle element → search the left half.

5. If the target is greater than the middle element → search the right half.

6. Repeat until the start pointer is greater than the end pointer (target not found).

---

Binary Search Visual

---

Pseudocode for Binary Search

sqlCopyEditfunction binarySearch(array, target):
    left ← 0
    right ← length(array) - 1

    while left ≤ right:
        mid ← (left + right) / 2

        if array[mid] == target:
            return mid

        else if target < array[mid]:
            right ← mid - 1

        else:
            left ← mid + 1

    return -1

---

Binary Search in JavaScript — Iterative Approach

javascriptCopyEditfunction binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid; // Found
        } else if (arr[mid] < target) {
            left = mid + 1; // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }
    return -1; // Not found
}

// Example usage
let numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72];
console.log(binarySearch(numbers, 23)); // Output: 5

---

Binary Search in JavaScript — Recursive Approach

javascriptCopyEditfunction binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) return -1; // Not found

    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    } else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

// Example usage
let numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72];
console.log(binarySearchRecursive(numbers, 72)); // Output: 9

---

Time & Space Complexity

• Space Complexity:

  • Iterative → O(1)

  • Recursive → O(log n) (due to call stack)

---

When to Use Binary Search

✅ The array/list is sorted.
✅ You need fast lookups in large datasets.
✅ Memory is not a major constraint.

---

Common Mistakes in Binary Search

❌ Forgetting that the array must be sorted before searching.
❌ Infinite loops caused by incorrect pointer updates.
❌ Integer overflow when calculating mid (use left + Math.floor((right - left) / 2)).

---

Practice Problems

1. Search for a number in a sorted array.

2. Find the first and last occurrence of a number in a sorted array.

3. Guess the number game (Leetcode 374).

---

💡 Up Next — Day 8: We’ll explore Real-World Applications of Binary Search, including variations like lower bound, upper bound, and more.

#CodeWithGift #DSA2025 #JavaScript #DaySeven