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: stackoverflow.com/questions/504103/… — folkol
– folkol, Commented Jun 3, 2015 at 20:45
What exactly is your issue? Please describe in detail what you are having problems with. — TimoStaudinger
– TimoStaudinger, Commented Jun 3, 2015 at 22:03

TimoStaudinger · Accepted Answer · 2015-06-03 22:17:21Z

1

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.

answered Jun 3, 2015 at 22:17

TimoStaudinger

42.7k16 gold badges91 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user4935102 Over a year ago

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 Over a year ago

Thank you so much for your help and sorry about the late reply.

Collectives™ on Stack Overflow

Random Number Array using binarySearch and Linear Search

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related