Random Number Array using binarySearch and Linear Search

Question

I have created the array and a method to sort the array, but I am still stuck on how to implement the binary search method in the array. Also the binary search method needs to be called from the array in the main class.

public class Search {

public static boolean binarySearch(int[] array, int value) {
    return binarySearchHelper(array, value, 0, array.length);
}

private static boolean binarySearchHelper(int[] array, int value, int low, int high) {
    if (low <= high) {
        int mid = (low + high) / 2;
        if (value == array[mid]) {
            return true;
        } else if (value < array[mid]) {
            return binarySearchHelper(array, value, low, mid - 1);
        } else {
            return binarySearchHelper(array, value, mid + 1, high);
        }
    }
    return false;
}

public static boolean linearSearch(int[] array, int value) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == value) {
            return true;
        } else if (array[i] > value) {
            return false;
        }
    }
    return false;
}

And Here is the Main

import java.util.Random;
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

        //System.nanoTime() will give me the current time (it's like looking at the clock)
        //I'll save the current time right (immediately) before I start the thing I want to time
        long start = System.nanoTime();

        long elapsed = System.nanoTime() - start;
        Random value = new Random();
        int size = 2000;
        int max = 5000;
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = value.nextInt();
        }
        Arrays.sort(array);
        for (int i = 100; i < 2000; i+=100) {
            start = System.nanoTime();
            for ( int j = 0; j < 2000; j++){
                Search.binarySearch(array, value.nextInt());
            }
        }
        elapsed = System.nanoTime() - start;
        System.out.println("Total time elapsed is: "+ elapsed);
    }
}

This will help with the comparison: http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — folkol, Jun 03 '15 at 20:45
What exactly is your issue? Please describe in detail what you are having problems with. — TimoStaudinger, Jun 03 '15 at 22:03

score 1 · Answer 1 · answered Jun 03 '15 at 22:17

Your binary search method itself looks good to me so far.

Your problem is in your main method:

for ( int j = 0; j < 2000; j++){
    return array;
}

First of all, any method will end and return to the caller when you use the return statement. For this reason, it would only execute one iteration of your loop, which is probably not your intended behavior.

However, this won't happen here anyways - you won't be able to compile this statement. A Java main method always has the return type void, which means that you cannot return any values when you use the return statement.

Since I assume that you are trying to create a benchmark, you are probably not really interested in the outcome of the search anyways, you are only interested in how long it will take to execute it.

To achieve this, why don't you just call it and discard the result?

for ( int j = 0; j < 2000; j++){
    Search.binarySearch(array, value.nextInt());
}

On a side note, value might be a sub optimal name for the variable that holds a reference to Random, since it does not tell you what's in it - valueGenerator or random may be better choices. This tip might be especially handy for bigger projects where it's not always obvious where the variable is instantiated.

When i changed what I had written and run it now gives me this resultException in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2000 at inlab4.Search.binarySearchHelper(Search.java:16) at inlab4.Search.binarySearchHelper(Search.java:21) — user4935102, Jun 03 '15 at 22:50
Thank you so much for your help and sorry about the late reply. — user4935102, Jun 07 '15 at 21:53

Random Number Array using binarySearch and Linear Search

1 Answers1