binary_search_and_lower_bound_and_upper_bound_in_vector

binary_search_and_lower_bound_and_upper_bound_in_vector.cpp

        std::cout << "binary search\n";
        {
            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(), n;
                do{
                    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;
                    }
                }while(n > 0);

                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();
            std::cout << std::endl;

            auto lower_bound = [&](double value) -> std::vector<double>::iterator{
                if(vec.empty() || *vec.rbegin() < value){
                    return vec.end();
                }else if(value < *vec.begin()){
                    return vec.begin();
                }

                std::size_t i = 0, j = vec.size(), n;
                do{
                    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 vec.begin() + prime;
                    }
                }while(n > 0);

                return vec.begin() + (i + 1);
            };

            auto print_lower_bound = [&](double value){
                auto r = lower_bound(value);
                std::cout << "lower_bound " << value << " : ";
                if(r != vec.end()){
                    std::cout << *r << std::endl;
                }else{
                    std::cout << "(nothing)" << std::endl;
                }
            };

            print_lower_bound(1.0);
            print_lower_bound(3.5);
            print_lower_bound(4.5);
            print_lower_bound(-1.0);
            print_lower_bound(128.0);
            print_lower_bound(128.5);
            std::cout << std::endl;

            auto upper_bound = [&](double value) -> std::vector<double>::iterator{
                if(vec.empty() || *vec.rbegin() < value || !(value < *vec.rbegin())){
                    return vec.end();
                }else if(value < *vec.begin()){
                    return vec.begin();
                }

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

                return vec.begin() + (i + 1);
            };

            auto print_upper_bound = [&](double value){
                auto r = upper_bound(value);
                std::cout << "upper_bound " << value << " : ";
                if(r != vec.end()){
                    std::cout << *r << std::endl;
                }else{
                    std::cout << "(nothing)" << std::endl;
                }
            };

            print_upper_bound(1.0);
            print_upper_bound(3.5);
            print_upper_bound(4.5);
            print_upper_bound(-1.0);
            print_upper_bound(128.0);
            print_upper_bound(128.5);
        }