Двоичный поиск уменьшающегося списка?

Question

У меня есть массив отсортированный в строго порядке убывания и элемент val; Я хочу, чтобы найти индекс наибольшего элемента в массиве, который меньше, чем val (или равен, если val уже существует там), и я хочу сделать это в logn времени. И обращение вспять массива и выполнение функции upper_bound() не является опцией.

Например. если массив равен {10,5,3,1} и val равен 6, функция должна возвращаться 1.

Я действительно новичок в итераторах и попытался что-то вроде добавления функции сравнения в upper_bound(), чтобы она работала это не удалось. Как я должен это делать.

Примечание: Я проверял подобные вопросы перед публикацией и нашел один, но, к сожалению, это относится к Java.

Answer 1

Просто используйте upper_bound с соответствующей функцией сравнения:

• Ваш список восстанавливается (upper_bound обычно ожидает, что рост порядка), поэтому вы должны использовать > вместо <.
• Вы хотите включить искомый элемент (в то время как upper_bound обычно исключает его), поэтому вам нужно использовать >=, а не просто >.

.

int data[] = {10,5,3,1}; 
auto item = std::upper_bound(std::begin(data), std::end(data), 6, 
          [](int a, int b) { return a >= b; }); 

Теперь вы только должны преобразовать получившийся итератор к индексу (после проверки он действителен):

if (item != std::end(data)) { 
    auto index = std::distance(std::begin(data), item); 
    std::cout << index << std::endl; 
} 
else 
    std::cout << "not found" << std::endl; 

Answer 2

Используйте upper_bound(), который выполняет функцию сравнения, как показано на рисунке.

Answer 3

Для итерационного пути то, что я, вероятно, сделаю, это начать поиск значений val с конца массива. то есть:

int indexFinder(int array[], int arraySize, int val){ 
    for(int i = (val >= arraySize ? 0 : (arraySize - val)); i < arraySize; ++i){ 
     if(array[i] <= val) return i; 
    } 
} 

Один ключ к этой петле является то, что, как только он встречает любое значение меньше или равно, она возвращает индекс, ограничивая его в первом случае он находит.

Он также проверяет, больше ли размер val, чем самый большой индекс массива.