Блог

Главная - Вопросы по программированию - Существует ли алгоритм двоичного поиска, который принимает унарный предикат, а не значение поиска?

Существует ли алгоритм двоичного поиска, который принимает унарный предикат, а не значение поиска?

#c #binary-search

Вопрос:

У меня есть это упражнение:

Учитывая массив целых чисел, найдите первое пропущенное положительное целое число в линейном времени и постоянном пространстве. Другими словами, найдите наименьшее положительное целое число, которого нет в массиве. Массив также может содержать дубликаты и отрицательные числа.
Например, ввод [3, 4, -1, 1] должен давать 2 и ввод [1, 2, 0] должен давать 3 .
Вы можете изменить входной массив на месте.

Моя реализация:

 template <typename In_It>
int missingPositiveInt(In_It first, In_It last){
    first = std::find_if( first, last, [](int x){return x > 0;} );
    if(first == last || *first > 1)
        return 1;
    for( auto next = first; (  next != last) amp;amp; ( !(*next - *first > 1) ); )
          first;

    return *first   1;
}

int main(){

    std::vector<int> v{5, 2, -1, 7, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << 'n';

    v = {2, -1, 1, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << 'n';

    v = {5, 2, -1, 7, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << 'n';

    v = {3, 4, -1, 1};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << 'n';

    v = {1, 2, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << 'n';

    std::cout << 'n';
}

Вывод:

 1
3
1
2
3

Программа работает просто отлично, но я использую алгоритм std::find_if для поиска первого положительного значения в последовательности (отсортированной последовательности), и этот алгоритм выполняет линейный поиск.

  • Пока входная последовательность уже отсортирована, я хочу использовать какой-нибудь алгоритм двоичного поиска для ускорения процесса.
  • Я пробовал использовать std::binary_search , но для этого требуется аргумент, который нужно искать. Что мне нужно, так это получить версию, которая использует унарный предикат и применяет двоичный поиск или любой другой более быстрый алгоритм, чтобы найти наименьшее положительное значение в последовательности, чтобы я мог написать: 
     auto it = binary_search(first, last, [](int x){ return x > 0; });

Возможно ли это? Мой код в порядке, или мне нужно его изменить. Поэтому любое предложение, подсказка высоко ценятся.

Комментарии:

1. Линейное время? Но сама по себе сортировка занимает больше, чем линейное время, не так ли?

2. В библиотеке должен быть алгоритм двоичного поиска, который вы можете вызвать с помощью унарного предиката, но его нет. Но даже если бы это было так, это не приведет вас к линейному времени здесь.

3. @numzero с кодом в вопросе да, но массив целых чисел можно отсортировать за линейное время

4. std::binary_search просто возвращает bool, а не итератор. std::lower_bound(first, last, 1) возможно, это то, что вы ищете в своем случае.

5. Это не проблема «двоичного поиска». Вы заметите, что ни один из примеров массивов не отсортирован. Двоичный поиск работает только с отсортированными массивами . Правильное решение этой головоломки кодирования не будет иметь никакого отношения к любому двоичному поиску. Это вопрос с подвохом, и ответ должен быть очень очевидным, как только вы уделите время, чтобы логически продумать поставленную задачу.

Ответ №1:

Да, std::partition_point делает именно то, что вы хотите.

Ответ №2:

Частичное решение, основанное на ответе @numzero. Это не обрабатывает отрицательные числа или нули в массиве, но вы можете справиться с этим, предварительно обработав массив линейно, чтобы удалить их заранее. Он просто отмечает каждый индекс как «найденный», отрицая его, а затем позже ищет первое не отрицательное значение, и это то самое. Несмотря на то, что это частичное решение, оно показывает основной алгоритм.

 #include <iostream>
using namespace std;

int main() {
    
    int arr[] = {1, 4, 6, 7, 2, 7, 7, 8, 3};
    
    int arrSize = sizeof(arr)/sizeof(int);
    
    for(int i=0; i<arrSize;   i)
    {
        int val = abs(arr[i]);
        if(val > 0 amp;amp; val-1 < arrSize)
        {
            if (arr[val-1]>0)
            {
                arr[val-1] = -arr[val-1];
            }
        }
    }
    
    for(int i=0; i<arrSize;   i)
    {
        if(arr[i] > 0)
        {
            std::cout << "Smallest is " << (i 1) << std::endl;
            return 0;
        }
    }
    
    std::cout << "Nothing found!" << std::endl;
    
    // your code goes here
    return 0;
}
Метки: , ,