Бинарный поиск по строкам вместо цифр

Question

Я читаю бинарный поиск по массиву чисел, и я считаю, что знаю, как это работает и как его реализовать. Теперь мне нужно знать, как выполнять бинарный поиск в массиве строк? Я знаю, что бинарный поиск требует, чтобы массив был отсортирован уже. предположим, что у меня есть массив строк, уже отсортированный, как мне реализовать бинарный поиск? Я знаю, если бы это был массив чисел, я бы пошел к среднему индексу массива и определил, будет ли требуемый поиск no слева или справа и сделать это рекурсивно. Как я могу это сделать для строк?

Answer 1

До тех пор, пока понятие типа «оно равно» и «оно меньше» определено для типа, над которым вы работаете, вы можете реализовать алгоритм. Не имеет значения, являются ли значения числами, буквами или пользовательскими объектами. Следующий пример демонстрирует эту концепцию:

template<typename Iterator>                   
Iterator search(Iterator initial, Iterator final, const typename Iterator::value_type& value) {  

    if(value < *initial) { 
    // bail out immediately  
    return final; 
    } 

    while(initial != final) {                   
    auto mid = std::next(initial, std::distance(initial, final)/2);        
    if(*mid == value) {                    
     return mid;                     
    } else if(*mid < value) {                  
     initial = std::next(mid);                  
    } else {                       
     final = std::prev(mid);                  
    }                        
    }                         
    return final;                      
}  

Покуда операций *mid == value и *mid < value определены, можно найти в контейнере любого типа (другое требование является то, что я должен быть в состоянии случайным образом получить доступ к своему итератору).

Это отнюдь не полный ответ, и есть много других деталей, но, надеюсь, вы получите эту идею.

Полный пример программы:

#include <vector> 
#include <list> 
#include <iostream> 

template<typename Iterator> 
Iterator search(Iterator initial, Iterator final, const typename Iterator::value_type& value) { 

    if(value < *initial) { 
    // bail out immediately  
    return final; 
    } 

    while(initial != final) { 
    auto mid = std::next(initial, std::distance(initial, final)/2); 
    if(*mid == value) { 
     return mid; 
    } else if(*mid < value) { 
     initial = std::next(mid); 
    } else { 
     final = std::prev(mid); 
    } 
    } 
    return final; 
} 


int main() { 
    { 
    std::vector<int> v {1, 2, 3, 4, 5}; 
    auto it = search(v.begin(), v.end(), 3); 
    if(it == v.end()) { 
     std::cout << "Not Found!" << std::endl; 
    } else { 
     std::cout << "Found in position: " << std::distance(v.begin(), it) 
       << " (value is : " << *it << ")" << std::endl; 
    } 
    } 

    { 
    std::vector<char> v {'a', 'b', 'c', 'd', 'e'}; 
    auto it = search(v.begin(), v.end(), 'd'); 
    if(it == v.end()) { 
     std::cout << "Not Found!" << std::endl; 
    } else { 
     std::cout << "Found in position: " << std::distance(v.begin(), it) 
       << " (value is : " << *it << ")" << std::endl; 
    } 
    } 

    { 
    std::list<float> v {-1, 0, 1, 2, 3, 4}; 
    auto it = search(v.begin(), v.end(), 0); 
    if(it == v.end()) { 
     std::cout << "Not Found!" << std::endl; 
    } else { 
     std::cout << "Found in position: " << std::distance(v.begin(), it) 
       << " (value is : " << *it << ")" << std::endl; 
    } 
    } 

    { 
    std::vector<char> v {'a', 'b', 'c', 'd', 'e'}; 
    auto it = search(v.begin(), v.end(), 'f'); 
    if(it == v.end()) { 
     std::cout << "Not Found!" << std::endl; 
    } else { 
     std::cout << "Found in position: " << std::distance(v.begin(), it) 
       << " (value is : " << *it << ")" << std::endl; 
    } 
    } 

}                       

Образец Run:

Found in position: 2 (value is : 3) 
Found in position: 3 (value is : d) 
Found in position: 1 (value is : 0) 
Not Found! 

Answer 2

Наивный подход состоит в том, чтобы присвоить уникальное значение каждой букве (если вы делаете английский, это легко, всего 26 значений) и сравнивайте значения первой буквы каждой строки. Если буквы совпадают, тогда вы сравниваете вторую букву и так далее.

Answer 3

Если вы используете массив std::string, то все равно, так как вы все сравниваете операторы.

, поэтому вам просто нужно заменить тип массива, и вы можете выполнить поиск как есть для чисел.

Answer 4

Точно так же. Если вы используете std::string, у него уже есть operator== и operator <, которые вам нужны только для двоичного поиска. Если у вас есть указатели на символы, вы можете использовать strcmp, где отрицательное значение меньше, а 0 равно.