二分查找

非递归实现

代码：

Position BinarySearch(List L, ElementType X) {
    Position mid,start, end;
    start = 1;
    end = L->Last;
    mid = (1 + L->Last) / 2;
//     if (X ==  L->Data[mid])
//         return mid;
    while (1) {
        if (X ==  L->Data[mid])
            return mid;
        else if (X <  L->Data[mid]) {
            end = mid - 1;
            mid = (start + end) / 2;
        }
        else if (X >  L->Data[mid]) {
            start = mid + 1;
            mid = (start + end) / 2;
        }
        else {
            
        }
        if(start>end)
            break;//这里注意退出条件！条件错误无法退出
    }
    return NotFound;
}

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];//增序
    Position Last; /* 保存线性表中最后一个元素的位置 */
};