Наиболее эффективный способ найти диапазон в массиве

Question

У меня есть отсортированный массив целых чисел, которые могут быть положительными негативом:

[ -30, -13, -10, -4, -1, 4, 23, 55, 90, 234, 433, 500 ] 

Мне нужно найти индексы наименьшее число, которое больше или равно нулю и наибольшее число, которое меньше или равно 400.
Каков наиболее эффективный способ сделать это?
(Я использую JavaScript, но любой язык или псевдокод будет в порядке)

Answer 1

O(log N)

JSFiddle: http://jsfiddle.net/vCY68/

function binaryIndexOf(data, criteria) { 
    'use strict'; 

    var minIndex = 0; 
    var maxIndex = data.length - 1; 
    var currentIndex; 
    var currentElement; 
    var result = null; 

    while (minIndex <= maxIndex) { 
     currentIndex = (minIndex + maxIndex)/2 | 0; 
     currentElement = data[currentIndex]; 
     var comparison = criteria(currentElement); 

     if (comparison[0] == 'right') { 
      minIndex = currentIndex + 1; 
     } else { 
      maxIndex = currentIndex - 1; 
     } 

     if (comparison[1]) { 
      result = currentIndex; 
     } 
    } 

    return result; 
} 

var firstPositive = binaryIndexOf(data, function(value) { 
    return value < 0 ? ['right', false] : ['left', true]; 
}); 

var lastLess400 = binaryIndexOf(data, function(value) { 
    return value > 400 ? ['left', false] : ['right', true]; 
}); 

Функция сравнения здесь возвращает 2 значения: первая, где двигаться после этого сравнения. 2nd, если текущее значение является приемлемым.

PS: чтобы сэкономить время на реализацию двоичного поиска кода из http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/ был взят, с незначительными изменениями

PPS: потенциально вы можете уменьшить количество сравнений при инициализации поиска диапазона вручную и параметризации второго поиска с firstPositive + 1 Начальный индекс

Answer 2

Сделайте двоичный поиск для 0 и 400 в вашем массиве. Если вы нажмете 0 или 400, то это ответ, в противном случае проверьте элемент массива, который вы достигнете, а также элементы слева или справа, чтобы увидеть, какой из них меньше, чем 0 или наибольший, чем 400. Сложность - это O (log n), если ваш массив имеет размер n.

Answer 3

Сделайте бинарный поиск для нижнего элемента, большего чем 0, и для его наивысшего элемента больше 400 в вашем массиве.

Вам нужно будет внести небольшие изменения в свой поиск, чтобы проверять каждый раз, если элемент рядом с вашим индексом все еще уменьшается или увеличивается. Например: если вы достигнете значения 3, а предыдущий элемент равен -2, тогда 3 будет вашим ответом (т. Е. Вместо сравнения для равенства вы ищете следующее самое высокое или самое низкое значение)

Вам понадобится 2 O (logn) для достижения этого.