vector - бинарный поиск

Question

Пытаюсь реализовать бинарный поиск в векторе. Когда я передаю vector_int - функция возвращает целочисленный индекс, если double - возвращает дробный. Как сделать, чтоб тоже возвращался целочисленный индекс?

template <typename T>
T binarySearch(std::vector<T>& array, T value) 
{
    T l = 0;
    T r = array.size();
    if (value > r)
    {
        std::cout << "Value not found!" << std::endl;
        return -1;
    }
    else 
    {
        T m = l + (r - l) / 2;

        while (l <= r && array[m] != value)
        {
            if (array[m] < value)
                l = m + 1;
            else                
                r = m - 1;
            
            m = l + (r - l) / 2;
        }
        if (array[m] == value) 
        {
            std::cout << "Value is found - " << m << std::endl;
            return m;
        }
        else
        {
            std::cout << "Value not found!" << std::endl;
            return -1;
        }
    }
}

int main()
{
    std::vector<int> array_int = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

    std::vector<double> array_double = {1, 2.4, 3.2, 4.4, 5.5, 6.7, 7.9, 8.1, 9.7, 10, 11.6, 12.4, 13.3, 14.5, 15.2, 16.6, 17.5, 18.5, 19.4, 20.1};

    binarySearch(array_double, 16.6);
   
    return 0;
}

Answer 1

Пропишите типы явно. Где то так

template <typename T>
int binarySearch(std::vector<T>& array, T value) 
{
    int l = 0;
    int r = array.size();
    if (value > array.back())
    {
        std::cout << "Value not found!" << std::endl;
        return -1;
    }
    else {
        int m = l + (r - l) / 2;

        while (l <= r && array[m] != value)
        {
            if (array[m] < value)
                l = m + 1;
            else
            {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        if (array[m] == value) {
            std::cout << "Value is found - " << m << std::endl;
            return m;
        }
        else
        {
            std::cout << "Value not found!" << std::endl;
            return -1;
        }
    }
}

Некоторые могут предложить место int использовать size_t, но так не стоит. Также я поправил начальное условие.

if (value > r)
{
    std::cout << "Value not found!" << std::endl;
    return -1;
}

просто посмотрите внимательно - если запрашиваемый элемент больше размера:)

Также, уберите вывод cout в внутри функции.

БЛОГ НА HUSL

vector - бинарный поиск

Ответы (1 шт):