CODEWITHSUNDEEP
javasearchbinary-search
user8138142
user8138142

Reputation:

Java binary search count number of comparisons

I wrote the following code for binary search in java:

import java.util.Arrays;

class BinarySearch  {
    public static int binarySearch(double[] arr, double x, int high, int low)   {
        int mid=(high+low)/2;
        if(high==low || low==mid || high==mid)  {
            return -1;
        }
        if(arr[mid]<x)  {
            return binarySearch(arr, x, high, mid);
        }
        else if(arr[mid]>x) {
            return binarySearch(arr, x, mid, low);
        }
        else if(arr[mid]==x)    {
            return mid;
        }
        return -1;
    }

    public static void main(String args[])  {
        int n=1000;
        double array[] = new double[n];
        for (int i=0; i<100; i++)   {
            for (int k = 0; k < n; k++) {
                double r = Math.random();
                r = r * 100;
                r = Math.round(r);
                r = r / 100;
                array[k] = r;
            }
            Arrays.sort(array);
            double search = Math.random();
            search = search * 100;
            search = Math.round(search);
            search = search / 100;
            int result=binarySearch(array, search, n, 0);
            if (result == -1)
                System.out.println(search +" befindet sich nicht im Array.");
            else
                System.out.println(search+" befindet sich im Array an der Stelle "+(result)+".");
    }
}

}

I would like to see the number of comparisons the binary search needs to do to find the number, but I don't know how to implement that. I already made a loop so I can see the average of the comparisons but I do not know how to get the number of comparisons.

Upvotes: 4

Views: 5262

Answers (4)

Cap
Cap

Reputation: 363

Declare a varible outside of binarysearch() 

import java.util.Arrays;
   class BinarySearch  {
      int num_of_calls = 0;
      public static int binarySearch(double[] arr, double x, int high, int low)   {
         num_of_calls++;
        ...
        }

num_of_calls will contain the amount of times the recursive function was called.

Upvotes: 0

Piyush
Piyush

Reputation: 1162

You can do this to keep things simple.

private static int comparisions = 0;

public static int binarySearch(double[] arr, double x, int high, int low) {
    int mid = (high + low) / 2;
    if (high == low || low == mid || high == mid) {
        comparisions++;
        return -1;
    }
    if (arr[mid] < x) {
        comparisions++;
        return binarySearch(arr, x, high, mid);
    } else if (arr[mid] > x) {
        comparisions++;
        return binarySearch(arr, x, mid, low);
    } else if (arr[mid] == x) {
        comparisions++;
        return mid;
    }
    return -1;
}

public static void main(String args[]) {
    int n = 1000;
    double array[] = new double[n];
    for (int i = 0; i < 100; i++) {
        for (int k = 0; k < n; k++) {
            double r = Math.random();
            r = r * 100;
            r = Math.round(r);
            r = r / 100;
            array[k] = r;
        }
        Arrays.sort(array);
        double search = Math.random();
        search = search * 100;
        search = Math.round(search);
        search = search / 100;
        int result = binarySearch(array, search, n, 0);
        System.out.println("Number of comparisions " +  comparisions);
        if (result == -1)
            System.out.println(search + " befindet sich nicht im Array.");
        else
            System.out.println(search + " befindet sich im Array an der Stelle " + (result) + ".");
    }

}

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727077

You can pass the number of comparisons down the invocation chain of your recursive method, like this:

public static int binarySearch(double[] arr, double x, int high, int low, int cmp) {
    ...
    if(arr[mid]<x)  {
        // We made one additional comparison
        return binarySearch(arr, x, high, mid, cmp+1);
    } else if(arr[mid]>x) {
        // We made two additional comparisons
        return binarySearch(arr, x, mid, low, cmp+2);
    } else {
        // We made two additional comparisons.
        // We are about to return the result, so print the final number of comparisons:
        System.out.println("Performed "+(cmp+2)+" comparisons.");
        return mid;
    }
}

Pass zero for cmp argument in the call from main.

Upvotes: 1

coinbird
coinbird

Reputation: 1217

Declare an int at the top of your code, and increment it before every return statement (because that's the final step of a comparison).

int compares = 0;

//other code

compares++;
return blahblah;

Upvotes: 2

Related Questions