CODEWITHSUNDEEP
javasearchcountbinary
rivyx
rivyx

Reputation: 11

Number of Comparisons Made by a Binary Search

Is it possible to count the number of comparisons made by a recursive binary search? If so, how?

Here is the search I am referring to:

//binary search
public static int binarySearch(int[] items, int start, int end, int goal)
{
    if (start > end)
        return (-1);
    else
    {
        int mid = (start + end)/2;
        if (goal == items[mid])
            return (mid);
        else
        if (goal < items[mid])
            return (binarySearch(items, start, mid - 1, goal));
        else
            return (binarySearch(items, mid + 1, end, goal));
    }
}//end binarySearch

Upvotes: 0

Views: 1389

Answers (2)

Matt
Matt

Reputation: 11815

Your most likely approach if you want to caller to be able to access the count is to pass in an accumulator into your binary search. In java 7 or less, AtomicLong may be a good choice (though it does have some overhead). In java 8, a LongAdder would also be good:

public static int binarySearch(int[] items, int start, int end, int goal, AtomicLong counter) {

}

and each time you do a comparison, you would just increment the count:

counter.incrementAndGet()

When you exit the search, the counter will contain the number of comparisons:

long count = counter.get()

Upvotes: 0

Aarowaim
Aarowaim

Reputation: 811

Declare your count variable outside of the method. Then add 1 each time that you call the method.

long count = 0;
//binary search
public static int binarySearch(int[] items, int start, int end, int goal)
{
    count += 1
    if (start > end)
        return (-1);
    else
    {
        int mid = (start + end)/2;
        if (goal == items[mid])
            return (mid);
        else
        if (goal < items[mid])
            return (binarySearch(items, start, mid - 1, goal));
        else
            return (binarySearch(items, mid + 1, end, goal));
     }
}//end binarySearch

Upvotes: 1

Related Questions