DSA using JavaScript

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

Binary Search

function countOccurrences(nums, target) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            count++;
        }
    }
    return count;
}

const nums = [1, 2, 2, 2, 3, 4, 5];
const target = 2;
console.log(countOccurrences(nums, target));  // Output: 3

function countOccurrences(nums, target) {
    function findFirst(nums, target) {
        let low = 0, high = nums.length - 1, first = -1;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (nums[mid] === target) {
                first = mid;
                high = mid - 1; // search in the left half
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return first;
    }

    function findLast(nums, target) {
        let low = 0, high = nums.length - 1, last = -1;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (nums[mid] === target) {
                last = mid;
                low = mid + 1; // search in the right half
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return last;
    }
    
    let first = findFirst(nums, target);
    if (first === -1) return 0; // target not found
    
    let last = findLast(nums, target);
    return last - first + 1;
}

const nums = [1, 2, 2, 2, 3, 4, 5];
const target = 2;
console.log(countOccurrences(nums, target));  // Output: 3