Average performance of binary search algorithm?

Posted by Passionate Learner on Stack Overflow See other posts from Stack Overflow or by Passionate Learner
Published on 2010-04-25T18:00:39Z Indexed on 2010/04/25 18:03 UTC
Read the original article Hit count: 410

Filed under:

algorithm

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance

BinarySearch(int A[], int value, int low, int high)
{
    int mid;
    if (high < low)
        return -1;
    mid = (low + high) / 2;
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1);
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high);
    else
        return mid;
}

If the integer I'm trying to find is always in the array, can anyone help me write a program that can calculate the average performance of binary search algorithm? I know I can do this by actually running the program and counting the number of calls, but what I'm trying to do here is to do it without calling the function. I'm not asking for a time complexity, I'm trying to calculate the average number of calls. For example, the average number of calls to find a integer in A[2], it would be 1.67 (5/3).

Average performance of binary search algorithm?

Posted by Passonate Learner on Stack Overflow See other posts from Stack Overflow or by Passonate Learner
Published on 2010-04-25T16:54:39Z Indexed on 2010/04/25 17:03 UTC
Read the original article Hit count: 410

Filed under:

BinarySearch(int A[], int value, int low, int high)
{
    int mid;
    if (high < low)
        return -1;
    mid = (low + high) / 2;
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1);
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high);
    else
        return mid;
}

If the integer I'm trying to find is always in the array, can anyone help me write a program that can calculate the average performance of binary search algorithm?

Developer IT