Monotone Array-algorithm analysis
A. Second Edition
This is one of problem in assignment of comp465 and it is regarded as a joke because professor said it is for fun.
But I spent quite a lot of time thinking about it.
Seriously this is not a joke. If I said anything about it before, I sincerely apologize for it because it may not
be as easy as it seems. I tried both linear-search and binary search for comparison. At beginning, it puzzles me
a lot as for almost all cases linear is BETTER then binary which is against my calculation! Finally I found out
my mistake that by applying master theorem, I already assume linear search is always in its worst cases. However,
it is very subtle for you to generate appropriate PATTERN of data to create WORST cases.
In all, it depends on the input data pattern. What I mean is that for a small n, the result is sometimes confusing.
When I use a large n, say 100, 200, the result makes much senses.
A two-dimensional array
a is called monotone ifa
(i, j) a(i + 1, j) and a(i, j) a(i, j + 1)for all
i and j. Design an algorithm that, given an n〜n monotone array a ofintegers, returns either a pair (
i, j) such that a(i, j) = 0 or a message toughluck
signifying that no such pair exists. Your objective is to minimize theworst-case number of entries of
a that your algorithm consults (n2 is trivialand
ndlg ne is easy; to get any points, you must do better than O(n lg n)).Present your algorithm in the pseudocode style of Question 1.
(This problem has nothing to do with any material covered in class; it is
simply a fun exercise in the design of ecient algorithms.)
1. An array of nxn and has such property that for every entry [i,j], it is always bigger than both upper and left engtry: [i-1,j] and [i, j-1]. This is called monotone array of size of n.
2. Can you find if the array has at least one entry which is 0? Don't say you can do it by binary search which is trivial. Don't say you need sort because it is a kind of sorted.
Originally it is proposed by some other guy, but he didn't believe it shortly. I had a feeling that it is divide-and-conquer like Strasseng's algorithm.
First you search along the diagonal of matrix until you encounter the positive entry. Then you divide matrix into four parts by row and column passing this entry: both the upper-left and lower-right will not contain 0 because one includes all negative and the other includes all positive. The upper-right and lower-left is your target which are two sub-matrix containing both positive and negative numbers. You recursive call to solve these two sub-matrix.
In this edition, I only add one binary search to compare with linear search along diagonal because it is a kind
of sorted. And the slightly change determine that the two algorithm has great difference in worst cases.
In linear search, the algorithm has much big difference in worst cases and best cases.
a) Best cases: There is no recursion and you find the zero or determined there is no zero when you finish
search along diagonal of matrix. Linear search is in O(n) and binary is in (lgn).
b) Worst cases: There is recursion. The search is always ended up at middle.
Linear: T(n)=n/2 + 2T(n/2)
Binary: T(n)=lg(n/2) + 2T(n/2)
Here we need to use Master Theorem.
For linear, f(n)=theta(n) and a=b=2 so, n^logb(a)=n^1 ===> f(n) = theta(n^logb(a))
Hence, T(n) = theta(nlgn)
For binary: f(n)=theta(lgn) and a=b=2 so, n^logb(a)=n^1 ====> f(n)=O(n^logb(a)-epsilon) where epsilon>0,
Hence, T(n) = theta(f(n))=theta(n^logb(a))=theta(n)
c) Average cases: There is recursion but it doesn't end up in the middle.
Linear: T(n)= n/b+ T(n/b)+ T(n/(n-b)) where 0<b<n
Binary: T(n)=lg(n/b) + T(n/b)+ T(n/(n-b)) where 0<b<n
Can we use Master Theorem here? I am not sure, but at least we can estimate approximately.
Let's choose b= max(b, n-b) to discuss the "worst" cases of this average cases:
Linear: T(n)= n/b+ 2T(n/b) where 2<b
Binary: T(n) = lg(n/b) + 2T(n/b) where 2<b
Then we can use Master Theorem similarly as worst cases:
Linear: f(n)=theta(n), a=2, b>2, logb(a)<1, ===> f(n)=omega(n^logb(a)+epsilon) where epsilon>0
Hence, T(n)=theta(f(n))= theta(n)
Binary: f(n)=theta(lgn) and a=2,b>2 so, logb(a)<1 ====> f(n)=O(n^logb(a)-epsilon) where epsilon>0,
Hence, T(n)=theta(n^logb(a))
Quite expectedly, binary search is better than linear search which is nothing special.
I tried to confirm my idea by running single test and multi-test which simply iterates a number of times and
calculates the average number of comparison operations of entries which is a scale of big O.
E.Further improvement
F.File listing
1. monotone.cpp
file name: monotone.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int _row, _col;
const int StartNumber=-500;
const int ArraySize=100;
//const int Step=8;
#define Step (rand()%10+3)
int array[ArraySize][ArraySize];
void initialize();
void binary(int startR, int startC, int step);
void linear(int startR, int startC, int step);
void display(int startR, int startC, int row, int col);
void construct(int row, int col);
bool search(int startR, int startC, int row, int col);
int counter=0;
bool showTrace=false;
bool noDisplay=true;
bool useLinear=true;
int max(int i, int j);
int min(int i, int j);
int testNumber=50;
double linearResult=0;
double binaryResult=0;
void monoRun();
void singleTest();
void multiTest();
int main(int argc, char* argv[])
{
srand(time(0));
/*
if (argc==2)
{
if (strcmp(argv[1], "trace")==0)
{
showTrace=true;
}
}
*/
//printf("single test no. 1\n");
//singleTest();
//printf("single test no. 2\n");
//singleTest();
printf("multi test \n");
multiTest();
return 0;
}
void singleTest()
{
showTrace=true;
noDisplay=false;
monoRun();
}
void multiTest()
{
double result=0;
showTrace=false;
noDisplay=true;
linearResult=binaryResult=0;
for (int i=0; i<testNumber; i++)
{
monoRun();
printf("\n**************************************************\n");
}
printf("\n%d times and average for linear is %g\n", testNumber, linearResult/testNumber);
printf("\n%d times and average for binary is %g\n", testNumber, binaryResult/testNumber);
}
void monoRun()
{
initialize();
if (!noDisplay)
{
display(0, 0, ArraySize, ArraySize);
}
printf("\n---------------------------------------------\nlinear test\n");
useLinear=true;
counter=0;
if (search(0, 0, ArraySize, ArraySize))
{
printf("\nfind it! array[%d][%d]=0\n", _row, _col);
printf("\nfind it! at counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
(double)counter/ArraySize);
}
else
{
printf("\nNo luck! counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
(double)counter/ArraySize);
}
linearResult+=(double)counter/ArraySize;
printf("\n----------------------------------------------\nbinary test\n");
counter=0;
useLinear=false;
if (search(0, 0, ArraySize, ArraySize))
{
printf("\nfind it! array[%d][%d]=0\n", _row, _col);
printf("\nfind it! at counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
(double)counter/ArraySize);
}
else
{
printf("\nNo luck! counter/ArraySize=%d/%d=%f\n", counter, ArraySize,
(double)counter/ArraySize);
}
binaryResult+=(double)counter/ArraySize;
//return (double)counter/ArraySize;
}
void linear(int startR, int startC, int step)
{
//entry.row=startR;
//entry.col=startC;
_row=startR;
_col=startC;
while (array[_row][_col]<0)
{
_row++;
_col++;
counter++;//comparison
if (_row+1==startR+step||_col+1==startC+step)
{
break;
}
}
}
void binary(int startR, int startC, int step)
{
//entry.row=startR+step-1;
//entry.col=startC+step-1;
_row=startR+step-1;
_col=startC+step-1;
while(true)
{
step/=2;
if (step==0)
{
break;
}
counter++;//comparison
if (array[_row-step][_col-step]>=0)
{
_row-=step;
_col-=step;
}
}
}
bool search(int startR, int startC, int row, int col)
{
//int r=startR, c=startC;
int step;
if (row==0||col==0)
{
return false;
}
if (row==1||col==1)
{
counter++;
return array[startR][startC]==0;
}
if (showTrace)
{
display(startR, startC, row, col);
}
step=min(row, col);
if (useLinear)
{
linear(startR, startC, step);
}
else
{
binary(startR, startC, step);
}
counter++;//comparison
if (array[_row][_col]==0)
{
//printf("\nfind it! array[%d][%d]=0\n", _row, _col);
return true;
}
return search(_row, startC, row-_row+startR, _col-startC)
||search(startR, _col, _row-startR, col-_col+startC);
}
void construct(int row, int col)
{
int left, upper, prev;
if (row==ArraySize||col==ArraySize)
{
return;
}
if (row-1>=0&&col-1>=0)
{
upper=array[row-1][col];
left=array[row][col-1];
}
else
{
if (row-1<0&&col-1>=0)
{
upper=left=array[row][col-1];
}
else
{
if (row-1>=0&&col-1<0)
{
upper=left=array[row-1][col];
}
else
{
//row=col==0, starting
upper=left=-50;
}
}
}
prev=upper>left?upper:left;
array[row][col]=prev+rand()%Step;//increase step everytime
construct(row+1, col);
construct(row, col+1);
construct(row+1, col+1);
}
void display(int startR, int startC, int row, int col)
{
printf("\n");
for (int r=startR; r<startR+row; r++)
{
printf("row[%d]\t", r);
for (int c=startC; c<startC+col; c++)
{
printf("%-5d", array[r][c]);
}
printf("\n");
}
}
int min(int i, int j)
{
return i<j?i:j;
}
int max(int i, int j)
{
return i>j?i:j;
}
void initialize()
{
counter=0;
for (int r=0; r<ArraySize; r++)
{
for (int c=0; c<ArraySize; c++)
{
if (r==0&&c==0)
{
array[r][c]=StartNumber;
}
else
{
if (r==0&&c!=0)
{
array[r][c]=array[r][c-1]+rand()%Step;
}
else
{
if (r!=0&&c==0)
{
array[r][c]=array[r-1][c]+rand()%Step;
}
else
{
array[r][c]=max(array[r-1][c], array[r][c-1])+rand()%Step;
}
}
}
}
}
//construct(0, 0);
}
How to run?
I try generate different pattern of data to create some kind of worst cases, best cases and average cases.
1. Adjust both StartNumber and Step appropriately to force the zero always appear near center. This is worst cases:
multi test
---------------------------------------------
linear test
find it! array[41][41]=0
find it! at counter/ArraySize=42/100=0.420000
----------------------------------------------
binary test
find it! array[42][42]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[63][24]=0
find it! at counter/ArraySize=65/100=0.650000
----------------------------------------------
binary test
find it! array[63][24]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[36][36]=0
find it! at counter/ArraySize=37/100=0.370000
----------------------------------------------
binary test
find it! array[36][36]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[38][38]=0
find it! at counter/ArraySize=39/100=0.390000
----------------------------------------------
binary test
find it! array[39][39]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[99][10]=0
find it! at counter/ArraySize=104/100=1.040000
----------------------------------------------
binary test
find it! array[82][13]=0
find it! at counter/ArraySize=36/100=0.360000
**************************************************
---------------------------------------------
linear test
find it! array[41][41]=0
find it! at counter/ArraySize=42/100=0.420000
----------------------------------------------
binary test
find it! array[95][11]=0
find it! at counter/ArraySize=23/100=0.230000
**************************************************
---------------------------------------------
linear test
find it! array[43][43]=0
find it! at counter/ArraySize=44/100=0.440000
----------------------------------------------
binary test
find it! array[43][43]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[66][23]=0
find it! at counter/ArraySize=68/100=0.680000
----------------------------------------------
binary test
find it! array[91][11]=0
find it! at counter/ArraySize=22/100=0.220000
**************************************************
---------------------------------------------
linear test
find it! array[93][12]=0
find it! at counter/ArraySize=108/100=1.080000
----------------------------------------------
binary test
find it! array[95][12]=0
find it! at counter/ArraySize=27/100=0.270000
**************************************************
---------------------------------------------
linear test
find it! array[45][45]=0
find it! at counter/ArraySize=46/100=0.460000
----------------------------------------------
binary test
find it! array[45][45]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[41][41]=0
find it! at counter/ArraySize=42/100=0.420000
----------------------------------------------
binary test
find it! array[86][16]=0
find it! at counter/ArraySize=18/100=0.180000
**************************************************
---------------------------------------------
linear test
find it! array[70][25]=0
find it! at counter/ArraySize=72/100=0.720000
----------------------------------------------
binary test
find it! array[70][25]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[41][41]=0
find it! at counter/ArraySize=42/100=0.420000
----------------------------------------------
binary test
find it! array[93][15]=0
find it! at counter/ArraySize=37/100=0.370000
**************************************************
---------------------------------------------
linear test
find it! array[44][44]=0
find it! at counter/ArraySize=45/100=0.450000
----------------------------------------------
binary test
find it! array[98][11]=0
find it! at counter/ArraySize=22/100=0.220000
**************************************************
---------------------------------------------
linear test
find it! array[66][24]=0
find it! at counter/ArraySize=68/100=0.680000
----------------------------------------------
binary test
find it! array[66][24]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[87][16]=0
find it! at counter/ArraySize=90/100=0.900000
----------------------------------------------
binary test
find it! array[88][16]=0
find it! at counter/ArraySize=18/100=0.180000
**************************************************
---------------------------------------------
linear test
find it! array[39][39]=0
find it! at counter/ArraySize=40/100=0.400000
----------------------------------------------
binary test
find it! array[39][39]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[83][17]=0
find it! at counter/ArraySize=86/100=0.860000
----------------------------------------------
binary test
find it! array[66][24]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[45][45]=0
find it! at counter/ArraySize=46/100=0.460000
----------------------------------------------
binary test
find it! array[45][45]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[39][39]=0
find it! at counter/ArraySize=40/100=0.400000
----------------------------------------------
binary test
find it! array[39][39]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[70][25]=0
find it! at counter/ArraySize=72/100=0.720000
----------------------------------------------
binary test
find it! array[70][25]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[69][26]=0
find it! at counter/ArraySize=71/100=0.710000
----------------------------------------------
binary test
find it! array[69][26]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[39][39]=0
find it! at counter/ArraySize=40/100=0.400000
----------------------------------------------
binary test
find it! array[39][39]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[68][23]=0
find it! at counter/ArraySize=70/100=0.700000
----------------------------------------------
binary test
find it! array[98][11]=0
find it! at counter/ArraySize=22/100=0.220000
**************************************************
---------------------------------------------
linear test
find it! array[42][42]=0
find it! at counter/ArraySize=43/100=0.430000
----------------------------------------------
binary test
find it! array[42][42]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[43][43]=0
find it! at counter/ArraySize=44/100=0.440000
----------------------------------------------
binary test
find it! array[43][43]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
---------------------------------------------
linear test
find it! array[98][13]=0
find it! at counter/ArraySize=102/100=1.020000
----------------------------------------------
binary test
find it! array[98][12]=0
find it! at counter/ArraySize=22/100=0.220000
**************************************************
---------------------------------------------
linear test
find it! array[66][23]=0
find it! at counter/ArraySize=68/100=0.680000
----------------------------------------------
binary test
find it! array[67][24]=0
find it! at counter/ArraySize=13/100=0.130000
**************************************************
---------------------------------------------
linear test
find it! array[47][47]=0
find it! at counter/ArraySize=48/100=0.480000
----------------------------------------------
binary test
find it! array[89][13]=0
find it! at counter/ArraySize=32/100=0.320000
**************************************************
---------------------------------------------
linear test
find it! array[41][41]=0
find it! at counter/ArraySize=42/100=0.420000
----------------------------------------------
binary test
find it! array[42][42]=0
find it! at counter/ArraySize=7/100=0.070000
**************************************************
30 times and average for linear is 0.588667
30 times and average for binary is 0.151333
1. Adjust both StartNumber and Step appropriately to force the zero not appear at center. This is both serves
average cases and best cases because I hardly don't want to force zero to appear at diagonal.
multi test
---------------------------------------------
linear test
find it! array[75][21]=0
find it! at counter/ArraySize=153/100=1.530000
----------------------------------------------
binary test
find it! array[75][21]=0
find it! at counter/ArraySize=108/100=1.080000
**************************************************
---------------------------------------------
linear test
find it! array[98][8]=0
find it! at counter/ArraySize=114/100=1.140000
----------------------------------------------
binary test
find it! array[89][13]=0
find it! at counter/ArraySize=57/100=0.570000
**************************************************
---------------------------------------------
linear test
find it! array[63][23]=0
find it! at counter/ArraySize=247/100=2.470000
----------------------------------------------
binary test
find it! array[77][17]=0
find it! at counter/ArraySize=80/100=0.800000
**************************************************
---------------------------------------------
linear test
find it! array[89][13]=0
find it! at counter/ArraySize=138/100=1.380000
----------------------------------------------
binary test
find it! array[90][13]=0
find it! at counter/ArraySize=58/100=0.580000
**************************************************
---------------------------------------------
linear test
find it! array[80][15]=0
find it! at counter/ArraySize=179/100=1.790000
----------------------------------------------
binary test
find it! array[79][16]=0
find it! at counter/ArraySize=78/100=0.780000
**************************************************
---------------------------------------------
linear test
No luck! counter/ArraySize=626/100=6.260000
----------------------------------------------
binary test
No luck! counter/ArraySize=357/100=3.570000
**************************************************
---------------------------------------------
linear test
find it! array[64][22]=0
find it! at counter/ArraySize=66/100=0.660000
----------------------------------------------
binary test
find it! array[66][20]=0
find it! at counter/ArraySize=95/100=0.950000
**************************************************
---------------------------------------------
linear test
find it! array[64][29]=0
find it! at counter/ArraySize=237/100=2.370000
----------------------------------------------
binary test
find it! array[64][29]=0
find it! at counter/ArraySize=132/100=1.320000
**************************************************
---------------------------------------------
linear test
find it! array[74][19]=0
find it! at counter/ArraySize=201/100=2.010000
----------------------------------------------
binary test
find it! array[74][19]=0
find it! at counter/ArraySize=65/100=0.650000
**************************************************
---------------------------------------------
linear test
find it! array[40][48]=0
find it! at counter/ArraySize=340/100=3.400000
----------------------------------------------
binary test
find it! array[40][48]=0
find it! at counter/ArraySize=221/100=2.210000
**************************************************
---------------------------------------------
linear test
find it! array[79][16]=0
find it! at counter/ArraySize=171/100=1.710000
----------------------------------------------
binary test
find it! array[33][50]=0
find it! at counter/ArraySize=211/100=2.110000
**************************************************
---------------------------------------------
linear test
find it! array[51][33]=0
find it! at counter/ArraySize=280/100=2.800000
----------------------------------------------
binary test
find it! array[52][33]=0
find it! at counter/ArraySize=178/100=1.780000
**************************************************
---------------------------------------------
linear test
find it! array[55][29]=0
find it! at counter/ArraySize=250/100=2.500000
----------------------------------------------
binary test
find it! array[86][12]=0
find it! at counter/ArraySize=56/100=0.560000
**************************************************
---------------------------------------------
linear test
find it! array[67][25]=0
find it! at counter/ArraySize=232/100=2.320000
----------------------------------------------
binary test
find it! array[67][25]=0
find it! at counter/ArraySize=129/100=1.290000
**************************************************
---------------------------------------------
linear test
find it! array[74][21]=0
find it! at counter/ArraySize=172/100=1.720000
----------------------------------------------
binary test
find it! array[53][33]=0
find it! at counter/ArraySize=150/100=1.500000
**************************************************
---------------------------------------------
linear test
find it! array[76][13]=0
find it! at counter/ArraySize=169/100=1.690000
----------------------------------------------
binary test
find it! array[75][13]=0
find it! at counter/ArraySize=82/100=0.820000
**************************************************
---------------------------------------------
linear test
find it! array[40][51]=0
find it! at counter/ArraySize=392/100=3.920000
----------------------------------------------
binary test
find it! array[41][51]=0
find it! at counter/ArraySize=247/100=2.470000
**************************************************
---------------------------------------------
linear test
find it! array[89][11]=0
find it! at counter/ArraySize=125/100=1.250000
----------------------------------------------
binary test
find it! array[89][11]=0
find it! at counter/ArraySize=45/100=0.450000
**************************************************
---------------------------------------------
linear test
find it! array[94][9]=0
find it! at counter/ArraySize=110/100=1.100000
----------------------------------------------
binary test
find it! array[94][10]=0
find it! at counter/ArraySize=39/100=0.390000
**************************************************
---------------------------------------------
linear test
find it! array[66][25]=0
find it! at counter/ArraySize=237/100=2.370000
----------------------------------------------
binary test
find it! array[55][31]=0
find it! at counter/ArraySize=116/100=1.160000
**************************************************
---------------------------------------------
linear test
find it! array[61][27]=0
find it! at counter/ArraySize=250/100=2.500000
----------------------------------------------
binary test
find it! array[62][27]=0
find it! at counter/ArraySize=129/100=1.290000
**************************************************
---------------------------------------------
linear test
find it! array[27][61]=0
find it! at counter/ArraySize=438/100=4.380000
----------------------------------------------
binary test
find it! array[27][61]=0
find it! at counter/ArraySize=286/100=2.860000
**************************************************
---------------------------------------------
linear test
find it! array[22][65]=0
find it! at counter/ArraySize=357/100=3.570000
----------------------------------------------
binary test
find it! array[22][65]=0
find it! at counter/ArraySize=221/100=2.210000
**************************************************
---------------------------------------------
linear test
find it! array[39][52]=0
find it! at counter/ArraySize=398/100=3.980000
----------------------------------------------
binary test
find it! array[39][52]=0
find it! at counter/ArraySize=261/100=2.610000
**************************************************
---------------------------------------------
linear test
find it! array[30][61]=0
find it! at counter/ArraySize=404/100=4.040000
----------------------------------------------
binary test
find it! array[30][62]=0
find it! at counter/ArraySize=293/100=2.930000
**************************************************
---------------------------------------------
linear test
find it! array[79][15]=0
find it! at counter/ArraySize=151/100=1.510000
----------------------------------------------
binary test
find it! array[79][15]=0
find it! at counter/ArraySize=84/100=0.840000
**************************************************
---------------------------------------------
linear test
find it! array[41][42]=0
find it! at counter/ArraySize=340/100=3.400000
----------------------------------------------
binary test
find it! array[41][42]=0
find it! at counter/ArraySize=216/100=2.160000
**************************************************
---------------------------------------------
linear test
No luck! counter/ArraySize=605/100=6.050000
----------------------------------------------
binary test
find it! array[93][8]=0
find it! at counter/ArraySize=29/100=0.290000
**************************************************
---------------------------------------------
linear test
No luck! counter/ArraySize=628/100=6.280000
----------------------------------------------
binary test
No luck! counter/ArraySize=413/100=4.130000
**************************************************
---------------------------------------------
linear test
No luck! counter/ArraySize=661/100=6.610000
----------------------------------------------
binary test
No luck! counter/ArraySize=424/100=4.240000
**************************************************
30 times and average for linear is 2.89033
30 times and average for binary is 1.62