0
\$\begingroup\$

I want to find the largest element in a sorted array, where the differences between the consecutive elements of the array are increasing, that is smaller than x.

For example:

  • [1, 3, 10, 17, 50, 1000] is a valid input , because the consecutive differences (2,7,7,33,950) are in increasing order.
  • [1, 3, 4, 10, 18] is not a valid input, as the consecutive differences (2, 1, 6, 8) are not in increasing order.

The optimum solution is O(log(log max_value)), so I am looking for better solutions than upperbound/ binary search. Actually ,I am looking to optimize binary search from O(log N) to O(log(log max_value).

#include <bits/stdc++.h>

using namespace std;

const int n=50000001;
int arr[n];

int binarysearch_lowerbound(int begin, int end, int x){
    int ans=end;
    while(begin<end){
    int mid=(begin+end)/2;
        if(arr[mid] >= x){
            ans = mid;
            end = mid;
        } else {
            begin = mid + 1;
        }
    }return ans;
}
int main() {
    int N;
    cin>>N;
    for (int i=0; i<N; i++){
        cin>> arr[i];
    }
    int q;
    cin>>q;
    for (int i=0; i<q; i++){
        int x;
        cin>>x;
        int k;
        int begin = x/(arr[N-1]-arr[N-2]);
        int end = x/(arr[1]-arr[0]);
        if(end>N-1){
            end=N;
        }
        k=binarysearch_lowerbound(begin,end,x);
        cout<<arr[k-1]<<endl;
    }
    return 0;
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Also. you say that you're looking for better than O(log n) scaling, but you don't say whether you have achieved that. \$\endgroup\$ Dec 29, 2020 at 18:55
  • \$\begingroup\$ You guessed right, I am texting with my mobile phone, had problem inserting the code.... I wrote a lowerbound function which gives me the right answer but in O(logn) , I tried to change the begin and end of the lowerbound function by dividing x with the first (smallest)and last ( largest) difference, but that’s also O( logN) \$\endgroup\$ Dec 29, 2020 at 19:15
  • 2
    \$\begingroup\$ You never use the fact that the differences between the consecutive elements of the array are increasing, and it is vital. Think Newton-Raphson \$\endgroup\$
    – vnp
    Dec 29, 2020 at 19:50
  • \$\begingroup\$ @vnp Yes, that’s actually what it all comes down to: how to use that fact, so that in each iteration of the binarysearch, the bounds are restricted by that fact..!!! \$\endgroup\$ Dec 30, 2020 at 11:44

1 Answer 1

2
\$\begingroup\$
#include <bits/stdc++.h>

Not a good start. This is not a standard C++ header; it's an artefact of your compiler's implementation, so non-portable, and subject to change without notice. Use the Standard-specified headers to define the library identifiers you need (any good reference tells you which to include).

using namespace std;

Please don't bring all of the Standard Library identifiers into the global namespace. It makes it much harder to reason about your code, and in extreme cases, can cause future versions of C++ to silently change the meaning of the program (when a new library function becomes a better match than one you define, for example).

const int n=50000001;

Where does this magic constant come from? What does it mean? n is not very descriptive for a global constant.

int arr[n];

Another global variable with an unhelpful name. What's it for? Why does it need to be global? Why are we using C-style arrays rather than std::array or std::vector?

int binarysearch_lowerbound(int begin, int end, int x){

This function isn't very reusable, as it depends on the global arr. If we passed pointers instead of integers for begin and end, then we would be able to find a value in any array we like. And why are we passing signed integers? Why would a negative value ever be useful?

    int ans=end;

We don't need this variable, since at the end of the loop ans==begin==end. So just return end when we get there.

    while(begin<end){

Nothing wrong with this line (although I would like the operators to have more "room to breathe").

      int mid=(begin+end)/2;

There's a problem here that's frequently found in binary search algorithms. The sum could overflow (which in signed integers, is Undefined Behaviour). A better way, given that we know begin is less than end, is

        int mid = begin + (end - begin) / 2;

This also has an advantage of being legal when we replace the indices with pointers.

That said, what we have here is plain binary search. We haven't used the information about the distribution (namely that the curve is concave, so all values are no higher than the straight line joining begin and end). We're only going to scale as O(log n).

int main() {
    int N;
    cin>>N;

Again, an utterly unhelpful variable name. I had to read the rest of main() to determine that this is supposed to be the array size to read.

After reading from a stream, we must confirm that the stream is not in error before using the value we read (e.g. if (!std::cin) { return EXIT_FAILURE; }).

    for (int i=0; i<N; i++){
        cin>> arr[i];
    }

If we'd used a std::vector for this, we could replace that loop with a simple standard copy:

std::copy_n(std::istream_iterator<int>(std::cin), N, std::back_inserter(arr));

Again, we need to check the error state after reading.

    int q;
    cin>>q;

What's q? I'm guessing a query into the array we have read.

    for (int i=0; i<q; i++){
        int x;
        cin>>x;

No, q must be the number of queries, and x is the actual query. These unhelpful names are really making the code harder to follow!

        int k;

Why declare k here? It's best to declare and initialise variables together, to reduce the risk of using it before it's initialised (though any decent compiler will warn if you do that).

        int begin = x/(arr[N-1]-arr[N-2]);
        int end = x/(arr[1]-arr[0]);

Here, we're using gradient to estimate the bounds for our search, but I'm not convinced the calculation is correct (shouldn't begin be subtracted from N?). When it has been corrected, I think we should be doing this inside binarysearch_lowerbound() at every iteration, since each subarray obeys the constraint on its shape.

        if(end>N-1){
            end=N;
        }
        k=binarysearch_lowerbound(begin,end,x);
        cout<<arr[k-1]<<endl;

There's no need to flush output using std::endl. Just output an ordinary return "\n" and let the stream do its buffering.

    }
    return 0;

In C++, we're allowed to omit return 0; from the end of main() (but only main(), not any other function). Success is assumed if we run off the end of the main function.


Modified code

Fixing the faults (other than the algorithm to reduce the search space, which is your own responsibility), I get:

/* Constraints (TODO: express using C++20 Concepts):
 *  * Iter must be a random-access iterator
 *  * Its value type must be an arithmetic type
 */
template<typename Iter, typename T>
Iter binarysearch_lowerbound(Iter begin, Iter end, const T x)
{
    --end;                      // make an inclusive range
    while (begin < end) {
        // TODO: improve algorithm to use curve constraint
    auto mid = begin + (end - begin + 1) / 2;
        if (x <= *mid) {
            end = mid - 1;
        } else {
            begin = mid;
        }
    }
    return begin;
}
#ifdef TEST

#include <array>
#include <cassert>
#include <iterator>

int main() {
    auto check = [](auto collection, auto value)
                 { using std::begin; using std::end; // for argument-dependent lookup
                     return *binarysearch_lowerbound(begin(collection), end(collection), value) ; };
    assert(check(std::array{ 0, 1, 1, 5, 10 }, 11) == 10);
    assert(check(std::array{ 0, 1, 1, 5, 10 },  8) == 5);
    assert(check(std::array{ 0, 1, 1, 5, 10 },  5) == 1);
    assert(check(std::array{ 0, 1, 1, 5, 10 },  -1) == 0);
}
#else  // not test

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    using value_type = int;     // would work for doubles, rationals, etc

    std::size_t array_size;
    if (!(std::cin >> array_size)) {
        return EXIT_FAILURE;
    }
    std::vector<value_type> values;
    values.reserve(array_size);
    std::copy_n(std::istream_iterator<int>(std::cin), array_size,
                std::back_inserter(values));
    if (!std::cin) {
        return EXIT_FAILURE;
    }

    std::size_t query_count;
    if (!(std::cin >> query_count)) {
        return EXIT_FAILURE;
    }

    while (query_count-->0) {
        value_type query;
        if (!(std::cin >> query)) {
            return EXIT_FAILURE;
        }
        std::cout << *binarysearch_lowerbound(values.begin(), values.end(), query);
    }
}

#endif
\$\endgroup\$
1
  • \$\begingroup\$ @ Toby Speight wow! thank you for thoroughly inspecting my code. Obviously, I am a new student of c++, thank you for making some points clear ( about bits, using namespace std, etc) My problem now, actually, comes down to using the fact about the differences ( the concave curve, as you say) and implementing that into my algorithm, so I restrict , in every iteration, the bounds of the function binarysearch _lowerbound. Again, thank you! \$\endgroup\$ Dec 30, 2020 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.