二分查找算法

    下面是两份二分查找算法的代码，记在这里，方面查看。
    第一份代码：

int BinarySearch(int array[], int length, int target)
{
    assert(length > 0);

    int lower = 0;
    int upper = length - 1;

    while(lower <= upper)
    {
        int mid = lower + (upper - lower) / 2;
        if(array[mid] == target)
        {
            return mid;
        }
        if(array[mid] > target)
        {
            upper = mid - 1;
        }
        else
        {
            lower = mid + 1;
        }
    }

    return -1;
}

    第二份代码：

int BinarySearch2(int array[], int length, int target)
{
    assert(length > 0);

    int lower = 0;
    int upper = length;                        //1

    while(lower < upper)                        //2
    {
        int mid = lower + (upper - lower) / 2;

        if(array[mid] > target)
        {
            upper = mid;                        //3
        }
        else if(array[mid] < target)
        {
            lower = mid + 1;
        }
        else
        {
            return mid;
        }
    }

    return -1;
}

    补充：设A[]是已经排好序的数组。请改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

int BinarySearch(int array[], int length, int target, int *i, int *j)
{
    assert(length > 0);

    int lower = 0;
    int upper = length - 1;

    while(lower <= upper)
    {
        int mid = lower + (upper - lower) / 2;
        if(array[mid] == target)
        {
            *i = mid;
            *j = mid;
            return 1;
        }
        if(array[mid] > target)
        {
            upper = mid - 1;
        }
        else
        {
            lower = mid + 1;
        }
    }
    *i = upper;
    *j = lower;

    return 0;
}