2

I am trying to test the time efficiency of the binary search for large sorted arrays in java.

This is the binary search method I am using, which takes in the search key and the array.

public int binarySearch(int[] a, int k) {
    int l = 0;
    int r = a.length - 1;

    int m = 0;

    while (l <= r) {
        m = (l+r)/2;
        if (k == a[m]) {
            return m;
        }
        else if (k < a[m]) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return -1;
}

I think creating the array programmatically might cause an overhead in the efficiency. Therefore I am trying to initialize large arrays as constant and use it in the program.

I tried both Array and ArrayList as shown below.

public static int D10000[] = {0, 1, 2, 3, ..... 10000};

public static ArrayList<Integer> D10000 = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, ...... 10000);

I am getting the following compilation error because the array size is too big.

Information:java: The system is out of resources. 
Information:java: Consult the following stack trace for details.
Information:java:   at com.sun.tools.javac.code.Type.map(Type.java:220)
Information:java: Errors occurred while compiling module 'SearchAlgo'
Information:javac 1.8.0_144 was used to compile java sources
Information:21/10/17, 12:02 PM - Compilation completed with 1 error and 0 warnings in 1s 481ms 
Error:java: java.lang.StackOverflowError

What is the best approach in achieving this?

Vishanth
  • 1,320
  • 3
  • 14
  • 26
  • If array size is too big to fit into the memory then you have to break the array into chunks of data and then search for that data in each chunk. – bit-shashank Oct 21 '17 at 02:12
  • @javafan thank you. I understand to achieve the functionality. But I am trying to analyse the efficiency of the binary search method in terms of time. So I am looking to send a single array into the method and calculate the time efficiency. – Vishanth Oct 21 '17 at 02:17
  • Don't initialize it at compile time: initialize it at runtime. – user207421 Oct 21 '17 at 02:20
  • 2
    Please be aware of this [What is microbenchmarking?](https://stackoverflow.com/questions/2842695/what-is-microbenchmarking) and that [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Zabuzard Oct 21 '17 at 02:39
  • @Zabuza thank you very much. That was useful. Seems like I will go ahead with the programmatically populating the array approach. – Vishanth Oct 21 '17 at 02:58

0 Answers0