How do I binary search with algorithms with std::list?

Binary searching is a highly efficient algorithm for finding a target within a sorted collection. However, due to the nature of `std::list` in C++, which does not allow for random access of elements, a traditional binary search is not directly applicable. Instead, we can utilize an iterator to traverse the list.

The following example demonstrates how to perform a binary search in a sorted `std::list` using iterators:


    #include <iostream>
    #include <list>
    #include <iterator>

    template <typename T>
    typename std::list<T>::iterator binarySearch(std::list<T>& lst, T target) {
        auto begin = lst.begin();
        auto end = lst.end();
        while (begin != end) {
            auto mid = std::next(begin, std::distance(begin, end) / 2);
            if (*mid == target) {
                return mid; // Target found
            } else if (*mid < target) {
                begin = std::next(mid); // Search right half
            } else {
                end = mid; // Search left half
            }
        }
        return lst.end(); // Target not found
    }

    int main() {
        std::list<int> numbers = {1, 3, 5, 7, 9, 11};
        
        auto it = binarySearch(numbers, 7);
        if (it != numbers.end()) {
            std::cout << "Found: " << *it << std::endl;
        } else {
            std::cout << "Not found" << std::endl;
        }
        
        return 0;
    }

binary search C++ std::list algorithms sorted list iterator searching algorithms

How do I binary search with algorithms with std::list?

Popular Topics

Recent Languages

How do I binary search with algorithms with std::list?

Related Questions

Popular Topics

Recent Languages