Help with binary search

[XodoX]

import java.util.Arrays;

public class binary_search {

public static void main(String[] args) {
int ar1[] = new int[128];


int p, key=78;
p=Arrays.binarySearch(ar1, key);
System.out.println("element found at index "+p);
Arrays.sort(ar1);
p=Arrays.binarySearch(ar1, key);

long start = System.currentTimeMillis();
Long elapsed = System.currentTimeMillis() - start
System.out.println("Time to do stuff (in milliseconds): " + elapsed );
}
}

I need to binary search to do unsucesfull searches. That's what it does. I also want it to measure the time of the search. Is this a correct implementation? How do I tell the search to do an x amount of searches?

[JamesCherrill]

You have most of what you need, so it's mainly a question of organising it. Here, in pseudo-code is the kind of thing that will work...

int[] testData = {78, 99, ... each value will be one search
get the start time
for (int key : testData) {
   search for key - so with n keys in testData you do n searches
}
get the end time
subtract the times to get total elapsed time
divide by the number of searches to get average search time.

NB: Your PC probably only does times to the nearest 1/60 sec, so you may have to have lot of test cases to get a long enough time to make a sensible meaurement.
You may also want to put some test data in ar1

[XodoX]

No, just anarray of size X. The array is going to be much larger and I can't put values in there. I just need unsuccessful searches for an array of the size X. Let's say 500,000 times.

import java.util.Arrays;
    public class binary_search {
    public static void main(String[] args) {
    int ar1[] = new int[128];
    int p, key=78;
    p=Arrays.binarySearch(ar1, key);

    Arrays.sort(ar1);
    p=Arrays.binarySearch(ar1, key);
    long start = System.currentTimeMillis();
    Long elapsed = System.currentTimeMillis(); 
    System.out.println("Time to do stuff (in milliseconds): " + elapsed );
    }
    }

This compiles, but there's no output, and I still have not figured out how to let it run X amount of times.

[JamesCherrill]

In that case there's no point sorting the array! (You could use the Random class to populate your array with random ints - that would be more realistic.)
Anyway, all you need is

get the start time
for (int count = 0, count < 500000; count++) { // for loop, 500,000 iterations
    do a search
}
get finish time
subtract the time, etc

[softswing]

import java.util.Arrays; public class binary_search { public static void main(String[] args) { int ar1[] = new int[128]; int p, key=78; p=Arrays.binarySearch(ar1, key); Arrays.sort(ar1); p=Arrays.binarySearch(ar1, key); long start = System.currentTimeMillis(); Long elapsed = System.currentTimeMillis(); System.out.println("Time to do stuff (in milliseconds): " + elapsed ); } }

HI XodoX,can you clear why two binarySearch method is using before sort and after sort?

[JamesCherrill]

Binary search requires that the array is sorted, so searching on an unsorted array is simply a mistake. (However, in this particular case the array is entirely full of zeros, so sorting it will make no difference!)