Day 8 – Binary Search: Variations & Applications

Yesterday, we learned the basic binary search algorithm and implemented it in JavaScript.
Today, we’ll push it further by looking at common variations and real-world problems that use binary search.

---

1. Recap of Binary Search

• Works only on sorted arrays.

• Repeatedly divides the search space in half.

• Time complexity: O(log n).

• Space complexity: O(1) for iterative, O(log n) for recursive.

---

2. Variation 1 – Finding First Occurrence

Sometimes, elements appear multiple times, and we want the first index.

Example:

javascriptCopyEditfunction firstOccurrence(arr, target) {
    let low = 0, high = arr.length - 1;
    let result = -1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            result = mid;
            high = mid - 1; // keep searching left
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

console.log(firstOccurrence([1,2,4,4,4,5,6], 4)); // Output: 2

---

3. Variation 2 – Finding Last Occurrence

Similar logic, but we search right after finding the target.

javascriptCopyEditfunction lastOccurrence(arr, target) {
    let low = 0, high = arr.length - 1;
    let result = -1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            result = mid;
            low = mid + 1; // keep searching right
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

console.log(lastOccurrence([1,2,4,4,4,5,6], 4)); // Output: 4

---

4. Variation 3 – Search in a Rotated Sorted Array

This is a common interview question.

Example problem:
Array [4,5,6,7,0,1,2] is sorted but rotated. Search for 0.

javascriptCopyEditfunction searchRotatedArray(arr, target) {
    let low = 0, high = arr.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) return mid;

        // Left half is sorted
        if (arr[low] <= arr[mid]) {
            if (target >= arr[low] && target < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (target > arr[mid] && target <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

console.log(searchRotatedArray([4,5,6,7,0,1,2], 0)); // Output: 4

---

5. Real-World Applications of Binary Search

• Searching in dictionaries.

• Autocomplete suggestion systems.

• Searching for words in spell checkers.

• Efficient lookups in databases.

• Finding boundaries (like first bad version in version control).

---

6. Homework

Easy

Find the first and last occurrence of a target in a sorted array using binary search (combine variation 1 and 2 into one function).

Intermediate

Implement binary search recursively.

Hard

Given a sorted array of unknown size (you can only access it using a get(index) function that returns Infinity if out of bounds), implement binary search.

#CodeWithGift #DSA2025 #JavaScript #DayEight