二分搜索

二分搜索算法实现。

 

算法中将计算中间值的部分写成一个函数的原因在于算法的可测性。实际上用函数来实现并不会影响程序的性能，原因在于现代编译器会优化一些代码，另外，将其写成inline函数就不会产生函数调用。

 

 

/**
 * Standard binary search
 * array input array sorted by ascending order
 * n size of array
 * x searched value
 * return index of x in the array from 0 if found. return -1 if not found
 */
int BinarySearch::Search( int *array, int n, int x )
{
    if (array == NULL || n < 1)
        return -1;

    int lower = 0;
    int upper = n -1;
    while (lower <= upper)
    {
        int mid = CalculateMidPoint(lower, upper);
        if (array[mid] == x)
            return mid;
        if (array[mid] > x)
            upper = mid - 1;
        else
            lower = mid + 1;
    }

    return -1;
}

/**
 * Find the first occurrence of the specified value in an array
 */
int BinarySearch::SearchFirst( int array[], int n, int x )
{
    if (array == NULL || n < 1)
        return -1;

    int lower = -1;
    int upper = n;
    int mid = -1;

    while (lower +1 != upper)
    {
        mid = CalculateMidPoint(lower, upper);

        if (array[mid] < x)
            lower = mid;
        else
            upper = mid;
    }

    if (upper >= n || array[upper] != x)
        return -1;
    else
        return upper;

文件:	algorithm.zip
大小:	15KB
下载:	下载

}

 

int CalculateMidPoint(int lower, int upper)
    {
        return lower + ((upper - lower) >> 1);
    }

 

程序中的单元测试采用visual assert.