binary_search_in_vector

binary_search_in_vector.cpp

void binary_search_test(){
    std::vector<double> vec = { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0 };

    auto insert = [&](double value) -> bool{
        if(vec.empty() || value < *vec.begin()){
            vec.insert(vec.begin(), value);
            return true;
        }else if(*vec.rbegin() < value){
            vec.insert(vec.end(), value);
            return true;
        }

        std::size_t i = 0, j = vec.size();
        while(true){
            std::size_t n = (j - i) / 2;
            std::size_t prime = i + n;
            if(value < vec[prime]){
                j = prime;
            }else if(vec[prime] < value){
                i = prime;
            }else{
                return false;
            }
            if(n == 0){ break; }
        }

        vec.insert(vec.begin() + (i + 1), value);
        return true;
    };

    auto print_vec = [&]() -> void{
        for(auto i : vec){
            std::cout << i << ", ";
        }
        std::cout << std::endl;
    };

    insert(-0.5);
    insert(0.5);
    insert(4.0);
    insert(3.0);
    insert(3.5);
    insert(6.5);
    insert(128.0);

    print_vec();
}