BinarySearch - Is this actually working right ?
Trying to find the average number of iterations to find something using both a sequential linear search, and also a binary search.
Is this working correctly ?
Code:
import java.lang.Math;
public class Linear {
public static void main(String args[]) {
final int DIM = 10000;
int [] searchlist = new int [DIM];
int h, i, j, k, total=0;
for(i = 0; i<DIM; i++)
searchlist[i] = i;
for(i = 0; i<DIM; i++) {
j = (int)(Math.random()*(DIM-1));
k = (int)(Math.random()*(DIM-1));
h = searchlist[j];
searchlist[j] = searchlist[k];
searchlist[k] = h;
}
for(i = 0; i<DIM; i++) {
j = 0;
while(searchlist[j] != i) {
j++;
total++;
}
total++;
}
System.out.println(" Linear : Avg number of comparisons is "+(total/DIM));
total = 0;
for(i = 0; i<DIM; i++) {
total = total + binarySearch(searchlist, i, 0, searchlist.length, 0);
}
System.out.println(" Binary : Avg number of comparisons is "+(total/DIM));
}
public static int binarySearch(int[] c, int x, int left, int right, int iteration) {
if (left == right) {
return iteration;
} else {
int mid = (int)((left + right)/2);
if (x <= c[mid])
return binarySearch(c, x, left, mid, iteration + 1);
else
return binarySearch(c, x, mid+1, right, iteration + 1);
}
}
}
