Help with binary search

I have a problem set I cannot seem to find a solution to...

I gotta array of pair of int
vector< pair<int, int > > array;

I have to find a pair where
the value of array[i].first * P + array[i].second * Q is the minimum

the problem is I cannot just loop trough it and find the minimum
because P and Q is input-ed multiple times and it doing a linear serach have a complexity of O(n^2) which is not fast enough

How do I sort the array so that I can binary search it ?
I cannot seem to get an Idea on how should I sort it
You might want to take a look at std::algorithm::sort

the documentation:
http://www.cplusplus.com/reference/algorithm/sort/
the useful tutorial:
http://www.cplusplus.com/articles/NhA0RXSz/

Also if you want the extra speed you may want to consider a C array instead of a C++ vector. Without knowing the number of elements it would be hard to be more specific. I would say if you don't plan to use any dynamic allocation, use a C array.

Alternatively, you could just write your own binary search, as it isn't very hard, although the STL offers so many implementations of the concept of binary search that you would be hard pressed to find something that hasn't already been done well.

Sean


hey hey there, I am asking on how should I sort it...
to make it more specific, what is the compare function ???

I know how to sort a the pair based on their first and second into order by using <algorithm> STL or even manually but sort them like that but does that help me solve the problem

Are P and Q integral types? Can either P, Q or the pair values be negative?
yes, P and Q is an integer
and
no, P and Q will not be negative
and array[i].first * P + array[i].second * Q will not execeed the 2 billion
is it not possible to use map. I mean

typedef vector< pair<int, int > > array;

multimap<int, array>

int key will summation of of the paired values.
Last edited on
??? I am a bit confused ?

Have anyone mention map ?
ok, multimap is possible

But,
How would a summation of the paired value help me deciding which pair is the best candidate for the answer ?

I can't seem to understand ?
K..
use the key for your multimap as
key = array[i].first * P + array[i].second * Q

then equal_range to find the iterators
Doesn't that makes things heavier ?
P and Q value change on every input
The array doesn't .....

Anyway changing the key every input wouldn't be a good idea ( I think )
can you explain more about your solution ...
Based on your inputs, this what i am assuming
x and y are int pair, P and Q i thought they were const but still k if they change for every input also

x y P Q key=(x*p + y*Q)
2 3 5 2 10+6 = 16
4 8 4 1 16+8 = 24
2 1 3 2 6+2 = 8
1 8 1 3 1+24 = 25

so, when you put this data in your multimap container this is how it looks

{8, (2,1)}
{16, (2,3)}
{24, (4,8)}
{25, (1,8)}
P and Q are input-ed multiple times
you can say that P and Q are arrays
but I don't keep them in array I just take P and Q then output the result right away

Calculating them one by one and search for the minimum would be an linear search, wouldn't it ?

I am trying to find a more optimal solution
The way I see the problem, it can only be solve by somehow binary search the array

but I don't based on what should I order it so that I can find the optimal solution without iterating trough the whole array
Your problem statement is that you have to find min of some thing like this
x * P + y * Q;

so better use the formula itself as the key and pair as its value. Did you read this e.g.
This is what i believe your problem statement

x y P Q key=(x*p + y*Q)
2 3 5 2 10+6 = 16
4 8 4 1 16+8 = 24
2 1 3 2 6+2 = 8
1 8 1 3 1+24 = 25

so better use the formula itself as the key and pair as its value

Better not to use the extra time and complexity that using a map would introduce. The linear search is more efficient than your proposed solution in terms of both complexity and memory.

My initial thoughts are that you might need to sort by the ratio of x:y (and perhaps the value of the smallest of the pair), but I haven't really had the chance to think it through.
anyone ? I still need your help

bump
Topic archived. No new replies allowed.