顺序查找

1 Position SequentialSearch(List Tbl, ElementType K)2 {3     Position i;4     Tbl->Data[0] = K;5     for (i = Tbl->Last; Tbl->Data[i] != K; i--);6     return i;7 }

二分查找

1 Position BinarySearch(List Tbl, ElementType K) 2 { 3     Position Left, Right, Mid; 4     Left = 1; 5     Right = Tbl->Last; 6      7     while (Left <= Right) 8     { 9         Mid = (Left + Right) / 2;10         if (Tbl->Data[Mid] < K) 11             Left = Mid + 1;12         else if (Tbl->Data[Mid] > K) 13             Right = Mid - 1;14         else15             return Mid;16     }17     return NotFound;18 }

测试这两个查找的剩余代码

1 #include 
     
       2 #include 
      
        3  4 #define MAXSIZE 15 5 typedef int ElementType; 6 typedef int Position; 7 #define NotFound 0        //找不到则返回0 8  9 struct Array{10     ElementType Data[MAXSIZE];11     int Last;12 };13 typedef struct Array* List;14 15 List CreateArray()16 {17     List Tbl = (List)malloc(sizeof(struct Array));        //已经为Data数组分配好了空间18     printf("%d\n", sizeof(struct Array));19     //Tbl->Data = (ElementType*)malloc(sizeof(ElementType) * MAXSIZE);20     Tbl->Last = 0;21     return Tbl;22 }23 24 void InsertA(List Tbl, ElementType X)25 {26     Tbl->Data[++Tbl->Last] = X;27 }
      
     

1 int main() 2 { 3     List Tbl = CreateArray(); 4     int result; 5     for (int i = 0; i <10; i++) 6         InsertA(Tbl, i + 15); 7     for (int i = 0; i < Tbl->Last; i++) 8         printf("%d ", Tbl->Data[i]); 9 10     //result = SequentialSearch(Tbl, 19);11     result = BinarySearch(Tbl, 19);12     if (result)13         printf("\nFind %d at index %d\n", 19, result);14     else15         printf("\nNot found\n");16 17     for (int i = 0; i < Tbl->Last; i++)18         printf("%d ", Tbl->Data[i]);19     return 0;20 }