Consider two 2D-Array $B_{ij} $ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.
For example
B = [
0001 => [ 32.5 => {10, 15, 20},
45.2 => {48, 16, 19},
...,
k1
],
0002 => [ 35.6 => {17, 35, 89},
68.7 => {18, 43, 74},
...,
k2
]
]
and similiarly for the sell array.
This is akin to an order association system of a stock/commodity exchange
BuyOrderBook = [
CompanyName => [
Price1 => [Qty1, Qty2...],
Price2 => [Qty1, Qty2...]
]
SecondCompany = [...]
]
What is the fastest way known to solve the following problem:
Input: Buy array $B$, Sell array $S$
Problem: Decide wether there are $(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ and $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ with $q_1, q_2 > 0$ and $p_2 \geq p_1$.
In short, what is the fatest way of matching orders for an exchange?
Update in response to comments
Lets say, MSFT has 25 shares @ \$60 to be sold and there is buyer who is willing to offer \$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \$60.
Now take the reverse case, MSFT has 25 shares @ \$60 to be bought and there is seller who is willing to receive \$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \$61 and the buyer is offering a maximum of \$60. The orders are now stored and await until new orders are received.
(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer specifies maximum price at which he is willing to buy).
Post execution, the sell order book will be (25-10)=15@86.5 while buy order book will be empty (10-10)=0.