Finding the closest true value for an index

Question

Is there an elegant STL way to find the closest true (1) value in an array for a given index. For example, for std::vector<int> v{1,1,1,0,0,0,1,1,0}; the closest true value for a given index 5 is at index 6.

I tried and ended up using multiple while loops with iterators. Is it possible using C++ STL?

Answer 1

This is the most concise version I could think of.

• Use cbegin to find from left->right, and crbegin() from right->left. But notice, there need to be some calculation to get the correct starting position in the latter circumstance.

You will need C++17 to support if init statement.

#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
int main()
{
    const std::vector<int> v{ 1, 1, 1, 0, 0, 0, 1, 1, 0 };

    const int index_to_find = 5;

    int rdistance = std::numeric_limits<int>::max();
    if (auto iter_right = std::find(std::cbegin(v) + index_to_find + 1, std::cend(v), 1); iter_right != std::cend(v))
        rdistance = std::distance(std::cbegin(v) + index_to_find, iter_right);

    int ldistance = std::numeric_limits<int>::max();
    if (auto iter_left = std::find(std::crbegin(v) + v.size() - index_to_find, std::crend(v), 1); iter_left != std::crend(v))
        ldistance = std::distance(std::crbegin(v) + v.size() - index_to_find - 1, iter_left);

    if (ldistance == std::numeric_limits<int>::max() && rdistance == std::numeric_limits<int>::max())
        std::cout << "Not found!\n";
    else
    {
        if (ldistance == rdistance)
            std::cout << "Found at index: " << index_to_find + ldistance << " and " << index_to_find - ldistance << "\n";
        else
            std::cout << "Found at index: " << (rdistance > ldistance ? index_to_find - ldistance : index_to_find + rdistance) << "\n";
    }
}

Answer 2

Here's an idea that you can expand on to cover all your use-cases.

You can use std::find and std::distance to achieve that.

Example (live):

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

int main()
{
    const std::vector<int> v { 1, 1, 1, 0, 0, 0, 1, 1, 0 };

    const auto it = std::find( std::begin(v) + 5, std::end(v), 1 );
    if ( it == std::end(v) )
    {
        std::cerr << "ERROR: Not found!\n";
        return EXIT_FAILURE;
    }

    const auto index = std::distance( std::begin(v), it );
    std::cout << "SUCCESS: Found at index " << index << '\n';

    return EXIT_SUCCESS;
}

You can wrap your own function with your default (i.e. true) for better readability according to your use-case. Also, look at std::next and std::advance for iterator navigation.

---

Another example using basic constructs only including some tests (live):

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <limits>

using Result = std::tuple<bool, std::size_t, std::string>; // result (T/F), index, message
Result find_nearest( const std::vector<int>& v, const std::size_t index, const int value )
{
    constexpr auto max_index = std::numeric_limits<std::size_t>::max();

    if ( v.empty() || index >= v.size() )
    {
        return { false, max_index, "Empty container or invalid index!" };
    }

    std::size_t ilhs { max_index };
    std::size_t irhs { max_index };

    for ( std::size_t i {0}; i != v.size(); ++i )
    {
        if ( v[i] == value )
        {
            if ( i < index ) { ilhs = i; }
            else if ( i > index ) { irhs = i; break; }
        }
    }

    // if element not found i.e. no index
    if ( ilhs == max_index && irhs == max_index )
    {
        return { false, max_index, "Index not found!" };
    }

    // shortest distance based comparison to determine indexes
    const auto dlhs = ( ilhs != max_index ? index - ilhs : ilhs );
    const auto drhs = ( irhs != max_index ? irhs - index : irhs );
    if ( dlhs == drhs )
    {
        return { true, ilhs, "Equal distance found! Left index returned!" };
    }

    const auto idx = ( dlhs < drhs ? ilhs : irhs );
    return { true, idx, "Index found!" };
}

int main()
{
    using Args  = std::tuple<std::vector<int>, std::size_t, int>; // list, index, value
    using Tests = std::vector<Args>;

    const Tests tests
    {
        { {}, 0, 1 },
        { { 1 }, 0, 1  },
        { { 1 }, 1, 1  },
        { { 1 }, 2, 1  },
        { { 0, 0, 0 }, 1, 1 },
        { { 0, 0, 0, 1, 0 }, 2, 1 },
        { { 1, 0, 0, 0, 1 }, 2, 1 },
        { { 1, 0, 0, 1, 0, 1, 0 }, 3, 1 },
        { { 1, 0, 0, 0, 1, 0, 0, 0, 1 }, 5, 1 },
    };

    for ( const auto& [list, index, value] : tests )
    {
        const auto& [found, idx, msg] = find_nearest( list, index, value );
        if ( found )
            std::cout << "INF: " << msg << " index: " << idx << '\n';
        else
            std::cerr << "ERR: " << msg << '\n';
    }

    return 0;
}

Output:

ERR: Empty container or invalid index!
ERR: Index not found!
ERR: Empty container or invalid index!
ERR: Empty container or invalid index!
ERR: Index not found!
INF: Index found! index: 3
INF: Equal distance found! Left index returned! index: 0
INF: Index found! index: 5
INF: Index found! index: 4