refactor very large c++ function

I have function like this (pseudo code):

constexpr int MAX_POS = 100;

std::string search(const std::string &key){
    int pos = 0;

    while(pos < MAX_POS){
        bool found = false;

        // lots of code

        if (found)
            return std::string{ data };

        // lots of code

        int where_to_go_next = 0;



        pos = calc_where_to_go_next(where_to_go_next);
    }

    return {}; // not found.
}

I want to refactor it like this:

constexpr int MAX_POS = 100;

std::string search(const std::string &key){
    int pos = 0;

    while(pos < MAX_POS){
        int where_to_go_next = sub_search(key);

        pos = calc_where_to_go_next(where_to_go_next);
    }

    return {}; // not found.
}

int sub_search(const std::string &key){
    bool found = false;

    // lots of code

    if (found)
        return std::string{ data }; // !!!

    // lots of code

    int where_to_go_next = 0;

    return where_to_go_next;
}

One of the problem is that sub_search sometimes return next node, sometimes return the result.

I can fix this with std::tuple, however, if I return pair, I need to check it inside search(), something like this:

std::tuple<bool, int, std::string> x = sub_search(key);
if (std::get<0>(x)){
   return std::get<2>(x);
}

int where_to_go_next = std::get(x);

This will make the function more confusing and less readable.

How can I improve this?