01-复杂度3 二分查找

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

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

Position BinarySearch( List L, ElementType X );

Position BinarySearch(List L, ElementType X)
{
    Position Left, Right, Mid;
    Left = 1;
    Right = L->Last;
    while(Left <= Right){
        Mid = (Left + Right) / 2;
        if(X > L->Data[Mid])
            Left = Mid + 1;
        else if(X < L->Data[Mid])
            Right = Mid - 1;
        else 
            return Mid;
    }
    return NotFound;
}