I wrote a program that tests speeds of linear and binary search and have found that at the beginning when the sorted array is the size of 1000 binary search uses a lot more time than later on when array size increases. Is there an explanation of why that is the case.
The program checks the algorithm 1000 times and calculates the average time it took to find the desired item for each array the size of n that contains elements from 1 to n.
import java.util.*;
public class Test {
public static void main(String[] args) {
System.out.println(" n | linear | binary |\n---------+--------------+---------------");
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}
static int[] generateTable(int n) {
int[] a = new int[n];
int ind = 0;
for (int i = 1; i <= n; i++) {
a[ind++] = i;
}
return a;
}
static int findLinear(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
if (a[i] == n) return i;
}
return -1;
}
static int findBinary(int[] a, int l, int r, int n) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (n < a[mid]) {
findBinary(a, l, mid - 1, n);
}
else if (n > a[mid]) {
findBinary(a, mid + 1, r, n);
}
return mid;
}
static long timeLinear(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findLinear(arr, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
static long timeBinary(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findBinary(arr, 0, arr.length - 1, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
}
Output:
n | linear | binary |
---------+--------------+---------------
1000| 5736| 1518|
2000| 787| 2012|
3000| 1313| 626|
4000| 1230| 711|
5000| 1281| 723|
6000| 1888| 463|
7000| 1846| 213|
8000| 1089| 187|
9000| 1213| 188|
10000| 1583| 216|
11000| 1607| 302|
12000| 3294| 311|
13000| 3656| 274|
14000| 3497| 274|
15000| 2315| 141|
16000| 1945| 135|
17000| 2223| 154|
18000| 2964| 136|
19000| 2464| 138|
20000| 2472| 138|
21000| 2829| 140|
22000| 3209| 157|
23000| 2901| 141|
24000| 3095| 140|
25000| 3157| 142|
26000| 3235| 162|
27000| 4118| 143|
28000| 3483| 145|
29000| 3906| 144|
30000| 3801| 145|
31000| 4322| 166|
32000| 4057| 146|
33000| 4516| 167|
34000| 4566| 147|
35000| 4453| 148|
36000| 4708| 148|
37000| 4772| 149|
38000| 5391| 168|
39000| 5500| 150|
40000| 5048| 150|
41000| 4979| 150|
42000| 5402| 151|
43000| 6160| 171|
44000| 6402| 153|
45000| 5855| 152|
46000| 5702| 152|
47000| 6184| 153|
48000| 5963| 154|
49000| 6927| 155|
50000| 6611| 154|
51000| 6326| 155|
52000| 6488| 155|
53000| 7690| 156|
54000| 7245| 156|
55000| 7074| 156|
56000| 6998| 154|
57000| 8299| 157|
58000| 7456| 156|
59000| 7776| 156|
60000| 8015| 189|
61000| 7762| 160|
62000| 8145| 158|
63000| 7946| 158|
64000| 9157| 156|
65000| 8299| 157|
66000| 8399| 159|
67000| 9119| 159|
68000| 8758| 159|
69000| 8921| 161|
70000| 9366| 162|
71000| 9326| 170|
72000| 9035| 161|
73000| 9873| 189|
74000| 9642| 189|
75000| 10272| 185|
76000| 10299| 163|
77000| 10602| 162|
78000| 9878| 165|
79000| 10790| 168|
80000| 10535| 165|
81000| 10627| 164|
82000| 11579| 166|
83000| 11003| 167|
84000| 11778| 164|
85000| 10686| 167|
86000| 11280| 168|
87000| 12562| 171|
88000| 11190| 197|
89000| 12949| 167|
90000| 11954| 169|
91000| 13170| 168|
92000| 12013| 169|
93000| 12245| 170|
94000| 12949| 194|
95000| 12264| 172|
96000| 13754| 170|
97000| 12919| 171|
98000| 14172| 170|
99000| 13436| 172|
100000| 14466| 171|
You should give a chance to JIT compiler for heating. Try this one instead:
for (int j = 0; j < 20; j++) {
System.out.printf("%n%nCycle # %d%n%n%n%n", j);
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}