0
$\begingroup$

I want to get a mathematica code for binary search algorithm applied to a sorted grid containing integers. For example, given

f[k_,x_]= x^2 + k x + k - 2

where k=2 n+3, n=0,1,2,... and x <= (k - 1)/2

From the above definitions, it is obvious that 2 < k <= 2 + Sqrt[f[k, x]^2 - 4 f[k, x] - 4].

A sorted grid from the above definitions looks like

k   3   5   7   9   11  13  ...
    5   17  35  59  89  125
    1   9   23  43  69  101
    -1  3   13  29  51  79
    -1  -1  5   17  35  59
    1   -3  -1  7   21  41
    5   -3  -5  -1  9   25
    11  -1  -7  -7  -1  11

I strongly believe that given any f, one can use binary search to locate this f in the grid where the low point will be 3 and the high point will be Ceiling[2 + Sqrt[f[k, x]^2 - 4 f[k, x] - 4]]-2.

For Example, if i want to find the location of f=9 on the grid, my low will be 3, my high will be 7. Now the nearest integer not less than 9 in the 3-column is 11 located at row 7 and the nearest integer not less than 9 in the 7-column is 13 located at row 3, so my flies behind. So I compute (3+7)/2 to obtain 5, where my f=9is finally located at row 2.

$\endgroup$
  • $\begingroup$ Did you realized that certain values of f(e.g. 9) appear multiples times in the grid? $\endgroup$ – Henrik Schumacher Jun 6 '18 at 9:47
  • $\begingroup$ @HenrikSchumacher Yes I know that some values appears more than once in the grid but am only interested in getting the location of one of the values. $\endgroup$ – Ik John Jun 6 '18 at 9:52
  • 3
    $\begingroup$ My intuition would say that your lack of sorting in this grid will cause you grief. If the rows were properly sorted you could simply binary search to pick the first row that could contain your value then binary search to pick that value in the row. That should be like $O(\lg n)+O(\lg m)$ for an $n{\times}m$ grid. $\endgroup$ – b3m2a1 Jun 6 '18 at 10:28
  • $\begingroup$ BinarySearch $\endgroup$ – corey979 Jun 6 '18 at 10:51
  • $\begingroup$ @corey979 Thanks for that link, I believe it may work but I do not know how to implement it. Please a little help is needed. $\endgroup$ – Ik John Jun 6 '18 at 11:21
2
$\begingroup$

So it turns out your grid really should be partially ordered. And it should look like this:

prettyString[Array[#2^2 + #*#2 + # - 2 &, {10, 10}], 100]

"{
    {1, 5, 11, 19, 29, 41, 55, 71, 89, 109},
    {3, 8, 15, 24, 35, 48, 63, 80, 99, 120},
    {5, 11, 19, 29, 41, 55, 71, 89, 109, 131},
    {7, 14, 23, 34, 47, 62, 79, 98, 119, 142},
    {9, 17, 27, 39, 53, 69, 87, 107, 129, 153},
    {11, 20, 31, 44, 59, 76, 95, 116, 139, 164},
    {13, 23, 35, 49, 65, 83, 103, 125, 149, 175},
    {15, 26, 39, 54, 71, 90, 111, 134, 159, 186},
    {17, 29, 43, 59, 77, 97, 119, 143, 169, 197},
    {19, 32, 47, 64, 83, 104, 127, 152, 179, 208}
}"

Looking at this it is pretty clear that we can do a binary search on the first row, take the column index we have, move to the next row, binary search again, but only starting from that new column index, etc.

In the worst case this would allow us to halve our runtime or something. Maybe you can do better by being more clever, but I am not clever so I will not do better.

And since this is such a trivial thing, we'll use Compile to make it appear as if it works well even if it doesn't:

gridBSIndex =
  Compile[
   {{grid, _Integer, 2}, {target, _Integer}},
   Module[
    {
     res = {-1, -1},
     testVal,
     rowPos = 1,
     colMin = 1,
     colMax = Dimensions[grid][[2]],
     colMean = Floor[(1 + Dimensions[grid][[2]])/2]
     },
    Do[
     testVal = grid[[row, colMean]];
     While[colMin != colMax,
      Which[
       testVal == target,
       colMin = colMax = colMean;,
       testVal > target,
       If[colMin == colMax - 1,
        colMin = colMax;,
        colMax = colMean;
        ],
       testVal < target,
       If[colMin == colMax - 1,
        colMin = colMax;,
        colMin = colMean;
        ]
       ];
      colMean = Floor[(colMin + colMax)/2];
      testVal = grid[[row, colMean]]
      ];
     If[testVal == target,
      res = {row, colMean};
      Break[],
      colMax = colMean;
      colMin = 1;
      colMean = Floor[(colMin + colMax)/2]
      ],
     {row, Length@grid}
     ];
    res
    ],
   RuntimeOptions -> "Speed"
   ];

And then we'll make a big array and randomly sample it:

wtfGrid = Array[#2^2 + #*#2 + # - 2 &, {1000, 1000}];
flatGrid = Flatten@wtfGrid;
choices = RandomChoice[flatGrid, 1000];

First a trivial check to see that it works:

gridBSIndex[wtfGrid, #] & /@ {29, 30}

{{1, 5}, {-1, -1}}

FirstPosition[wtfGrid, 29]

{1, 5}

FirstPosition[wtfGrid, 30]

Missing["NotFound"]

Then we can see how well this thing does:

RepeatedTiming[gridBSIndex[wtfGrid, #] & /@ choices][[1]]/1000

0.000807

Which is, I think, not terrible, all told. It is certainly faster than FirstPosition:

FirstPosition[wtfGrid, 29] // RepeatedTiming

{0.060, {1, 5}}
$\endgroup$
  • $\begingroup$ The prettystring[ ] function contains some rows with even integers, how do i delete them, because i do not want them. Thanks. $\endgroup$ – Ik John Jun 6 '18 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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