Как получить первый и последний индексы элемента в отсортированном массиве за логарифмическую сложность?

Question

[dc65k]

Есть отсортированный массив, необходимо вернуть первый и последний индексы указанного числа.

Решение за O(n):

const a = [1, 2, 3, 4, 5, 5, 5, 5, 7, 9, 9, 9, 9];

const search = (array, n) => {

    const a = array.reduce((accumulator, currentValue, idx) => {

        if (currentValue === n) {
            accumulator.push(idx);
        }

        return accumulator;
    }, []);

    if (!a.length) {
        return [];
    }

    return [
        a[0],
        a[a.length - 1]
    ];
}

console.log(search(a, 5)); // [4, 7]
console.log(search(a, 2)); // [1, 1]
console.log(search(a, 8)); // []

Пытаюсь решить, используя бинарный поиск (O (log n) Логарифмическая сложность), но не выходит:

const a = [1, 2, 3, 4, 5, 5, 5, 5, 7, 9, 9, 9, 9];

const binarySearch = (array, n) => {

    let output = [];

    let left = 0
    let right = array.length - 1
    let middle = null

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

        if (n === array[middle]) {
            output.push(middle);
            return output;
        } else if (n > array[middle]) {
            left = middle;
        } else {
            right = middle;
        }
    }

    return output;
}

console.log(binarySearch(a, 5)); // [4, 7]
console.log(binarySearch(a, 2)); // [1, 1]
console.log(binarySearch(a, 8)); // []

Answer 1

[0xD34F]

Два раза поиск делайте, отдельно для первого и последнего индексов:

function search(nums, target, searchMin) {
  for (let iMin = 0, iMax = nums.length - 1; iMin <= iMax; ) {
    const index = (iMin + iMax) / 2 | 0;
    const num = nums[index];

    if (num === target && num !== nums[index + (searchMin ? -1 : 1)]) {
      return index;
    } else if (num <= target - (searchMin ? 1 : 0)) {
      iMin = index + 1;
    } else {
      iMax = index - 1;
    }
  }

  return -1;
}

function searchMinMax(nums, target) {
  const iMin = search(nums, target, true);
  return iMin === -1
    ? []
    : [ iMin, search(nums, target, false) ];
}

Answer 2

[Alexandroppolus]

гугли по словам "upper_bound" и "lower_bound"

основное их отличие от поиска - нет досрочного выхода из цикла, если (n === array[middle]). То есть поиск идет до упора, пока интервал не схлопнется до нуля.

Пашка раскрыл тему здесь: https://www.youtube.com/watch?v=9Wjzf8KKvYQ