4a-quick-search-in-array.js

/*

A. Быстрый поиск в массиве

Ограничение времени	3 секунды (фактическое использование на тестах – до 447ms)
Ограничение памяти	64Mb (фактическое использование на тестах – до 40.77Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Дан массив из N целых чисел. Все числа от −10^9 до 10^9. 
Нужно уметь отвечать на запросы вида “Cколько чисел имеют значения от L до R?”.

Формат ввода
Число N (1 ≤ N ≤ 10^5). Далее N целых чисел.
Затем число запросов K (1 ≤ K ≤ 10^5).
Далее K пар чисел L, R (−10^9 ≤ L ≤ R ≤ 10^9) — собственно запросы.

Формат вывода
Выведите K чисел — ответы на запросы.

Пример

Ввод
5
10 1 10 3 4
4
1 10
2 9
3 4
2 2

Вывод
5 2 2 0 

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const size = parseInt(input[0]);
const dataArray = new Array(size);

const dataString = input[1].trim() + ' ';
const length = dataString.length;

let valueIndex = 0;
let valueString = '';

for (let pos = 0; pos < length; ++pos) {
    if (dataString[pos] === ' ') {
        dataArray[valueIndex++] = parseInt(valueString);
        valueString = '';
    } else {
        valueString += dataString[pos];
    }
}

dataArray.sort((a, b) => a - b);

let result = '';

for (let i = 3; i < input.length; ++i) {
    const [min, max] = input[i].trim().split(' ').map((value) => parseInt(value));

    if (max < dataArray[0] || min > dataArray[size - 1]) {
        result += '0 ';
        continue;
    }

    let left = 0;
    let right = size - 1;
    let middle;

    while (left < right) {
        middle = Math.floor((left + right) / 2);
        if (dataArray[middle] >= min) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }

    const minIndex = left;

    left = 0;
    right = size - 1;
    while (left < right) {
        middle = Math.floor((left + right + 1) / 2);
        if (dataArray[middle] <= max) {
            left = middle;
        } else {
            right = middle - 1;
        }
    }

    const maxIndex = left;

    const count = maxIndex - minIndex + 1;

    result += count + ' ';
}

fs.writeFileSync('output.txt', `${result.trim()}`);