标签： 算法

用数组实现静态顺序查找二分查找

查找：根据某个给定值K，从集合R中找到与K相同记录，这就是查找。
1.顺序查找算法
“哨兵”在顺序查找是的运用
时间复杂度是O(n)。
2.二分查找算法
二分查找算法要求
对数时间复杂度O(logN)。

二分查找算法

本题要求实现二分查找算法。函数接口定义：Position BinarySearch( List L, ElementType X );其中List结构定义如下：typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。裁判测试程序样例：

最大子列和问题

给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。