@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)); // []
  • Вопрос задан
  • 95 просмотров
Решения вопроса 1
0xD34F
@0xD34F Куратор тега JavaScript
Два раза поиск делайте, отдельно для первого и последнего индексов:

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) ];
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@Alexandroppolus
кодир
гугли по словам "upper_bound" и "lower_bound"

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

Пашка раскрыл тему здесь: https://www.youtube.com/watch?v=9Wjzf8KKvYQ
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы