DSA using JavaScript

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

Binary Search

function searchBruteForce(reader, target) {
    let i = 0;
    while (reader.get(i) !== 2147483647) {
        if (reader.get(i) === target) return i;
        i++;
    }
    return -1;
}

class ArrayReader {
    constructor(arr) {
        this.arr = arr;
    }

    get(index) {
        if (index >= this.arr.length) return 2147483647;
        return this.arr[index];
    }
}

const reader = new ArrayReader([-1, 0, 3, 5, 9, 12]);
const target = 9;
console.log(searchBruteForce(reader, target));  // Output: 4

function searchEfficient(reader, target) {
    let left = 0;
    let right = 1;

    // Find the upper bound
    while (reader.get(right) !== 2147483647 && reader.get(right) < target) {
        left = right;
        right *= 2;
    }
    
    // Binary search
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const num = reader.get(mid);
        
        if (num === target) return mid;
        if (num > target || num === 2147483647) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

class ArrayReader {
    constructor(arr) {
        this.arr = arr;
    }

    get(index) {
        if (index >= this.arr.length) return 2147483647;
        return this.arr[index];
    }
}

const reader = new ArrayReader([-1, 0, 3, 5, 9, 12]);
const target = 9;
console.log(searchEfficient(reader, target));  // Output: 4