Пользовательский бинарный поиск в векторе

Question

Предположим, у меня есть vector<int> myVec. Пусть в нем будет n элементов. Я знаю, что эти элементы находятся в упорядоченном порядке (по возрастанию), а также что они уникальны. Пусть n = 10 и myVec быть {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}. Мне даны l и r такие, что 0<=l<=r<=n-1. Теперь я хочу, чтобы найти элемент val в подвектора, который определяется в пределах l и r таким образом, что

1. если val найден возвращение val
2. если val не найден, то вернуть (если это возможно) значение в подвектор, который меньше, чем val.
3. Возврат false (или -1, возможно), если одно из указанных выше невозможно.

В вышеуказанном случае, если l = 3 и r = 5. Подвектор {8, 10, 12}. Если val = 8 вернуть 8. Если val = 7 возвращает false (или -1). Если val = 9 возврат 8.

Как это реализовать. Я хочу, чтобы заказ сопоставим с бинарным поиском. Кроме того, можно использовать std::binary_search() под заголовком algorithm файл заголовка.

Answer 1

Используя традиционный бинарный поиск с незначительными изменениями:

#include <iostream> 
#include <vector> 


int search(const std::vector<int> &vec, int l, int r, int val) 
{ 
     int pivot, xl = l, xr = r, mid; 

     do { 
       /* Not exact match, check if the closest lower match is in the 
       * subvector. */ 
       if (xl > xr) { 
         return xr >= l ? vec[xr]: -1; 
       } 

       mid = (xl + xr)/2; 
       pivot = vec[mid]; 
       if (val < pivot) { 
         xr = mid - 1; 
       } else if (val > pivot) { 
         xl = mid + 1; 
       } else if (val == pivot) { 
         return val; 
       } 
     } while (true); 
} 

int main() 
{ 
     std::vector<int> myVec(10); 
     myVec[0] = 2; 
     myVec[1] = 4; 
     myVec[2] = 6; 
     myVec[3] = 8; 
     myVec[4] = 10; 
     myVec[5] = 12; 
     myVec[6] = 14; 
     myVec[7] = 16; 
     myVec[8] = 18; 
     myVec[9] = 20; 

     int l = 3, r = 5; 

     std::cout << "search(3, 5, 8) = " << search(myVec, 3, 5, 8) << std::endl; 
     std::cout << "search(3, 5, 7) = " << search(myVec, 3, 5, 7) << std::endl; 
     std::cout << "search(3, 5, 9) = " << search(myVec, 3, 5, 9) << std::endl; 

     return 0; 
} 

    enter code here 

Answer 2

что-то вроде этого?

int search(int l, int r, int value) { 
    if (l > vec.Size() || r > vec.Size() || l > r) return -1; 
    for (int i = r; i >= l; --i) { 
    int v = vector[i]; 
    if (v <= value) return v; 
    } 
    return -1; 
} 

или ему нужно быть двоичным?

int BinarySearch(int l, int r, int value) { 
    return PrivateBinarySearch(l, r, (l+r)/2, value); 
} 

int PrivateBinarySearch(int l, int r, int index, int value) { 
    if (vector[index] == value) return value; 
    else if (vector[index] > value) { 
    if (index == l) return -1; 
    else if (index == r) return -1; 
    else return PrivateBinarySearch(l, index, (index-1+l)/2, value); 
    } 
    else { // vector[index] < value 
    if (index == l) return vector[index]; 
    else if (index == r) return vector[index]; 
    else return PrivateBinarySearch(index, r, (index+1+r)/2, value); 
    } 

Надеется, что это помогает

Answer 3

Это должно работать для вас и довольно расширяемого и гибко:

template<typename T> 
typename vector<T>::const_iterator 
find_or_under (typename vector<T>::const_iterator start, typename vector<T>::const_iterator end, 
       const T& val) 
{ 
    auto el = std::lower_bound(start, end, val); 

    //if not found, propagate 
    if (el == end) 
     return el; 

    //if it's equal, just return the iterator 
    if ((*el) == val) 
     return el; 

    //if there is no value of an equal or smaller size, return the end 
    if (el == start) 
     return end; 

    //otherwise, return the previous element 
    return el-1; 
} 

//Functor representing the search 
struct CustomSearch 
{ 
    //Create a searcher from a subrange 
    CustomSearch (const vector<int> &v, size_t l, size_t r) 
    { 
     start = std::lower_bound(std::begin(v), std::end(v), l); 
     end = find_or_under(start, std::end(v), r) + 1; 
    } 

    //Calling the searcher 
    //Returns this->end on not found 
    auto operator() (int val) 
    { 
     return find_or_under(start, end, val); 
    } 

    vector<int>::const_iterator start; 
    vector<int>::const_iterator end; 
}; 

int main() { 
    vector<int> v = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
    CustomSearch searcher {v, 3, 8}; 
    cout << *searcher(6); 
}