数组的不对称边界

/**
 * @file bsearch.c
 * @brief binary search,
 *        C Traps and Pitfalls, P132
 *        主题: 数组的不对称边界
 *        lower与higher是不对称边界的两头，即lower<=k<higher
 *        可以表示为[lower, higher)
 *        这样表示的效果:
 *        1. 取值范围的元素个数就是上界与下界之差
 *        2. 如果上界等于下界，那么取值范围为空
 *        3. 即使取值范围为空，上界也永远不可能小于下界
 *
 *        设mid = (lower+higher)/2
 *        若target小于下标为mid的元素，取higher=mid，表示mid是位于可能范围以外的最小下标
 *        若target大于下标为mid的元素，取lower=mid+1，表示mid+1是位于可能范围内的最小下标
 *        lower==higer的时候，表示可能范围为空，可判定target不存在
 *
 * @author simplyzhao
 * @version 0.0
 * @date 2009-05-05
 */

#include<stdio.h>
#include<stdlib.h>
/**
 * @brief 数组版本
 *
 * @param arr[]
 * @param length
 * @param target
 *
 * @return 返回指向目标元素的指针，不存在则返回NULL
 */
int *bsearch_arr(int arr[], int length, int target)
{
        int lower = 0;
        int higher = length;  /* 这里higher取的是length，而不是length-1 */
    int mid;

        while(lower < higher) {
                mid = (lower+higher)/2; /* 这里的除法运算可以替代为: (lower+higher)>>1, 当然前提是lower+higher非负 */
                if(arr[mid] > target)
                        higher = mid;
                else if(arr[mid] < target)
                        lower = mid+1;
                else
                        return arr+mid;
        }

        return NULL;
}

/**
 * @brief 指针版本
 *
 * @param arr
 * @param length
 * @param target
 *
 * @return
 */
int *bsearch_ptr(int *arr, int length, int target)
{
        int *lower = arr;
        /* 可以使用数组“溢界”元素的地址，这个地址可以用于赋值和比较，当然解引用肯定是非法的 */
        int *higher = arr+length;
        int *mid;

        while(lower < higher) {
                mid = lower + ((higher-lower) >> 1); /* 注意：这里指针不能进行相加运算 */
                if(*mid > target)
                        higher = mid;
                else if(*mid < target)
                        lower = mid+1;
                else
                        return mid;
        }

        return NULL;
}