查找与排序练习

由n个正整数构成的集合A{ak}, 将其划分为两个不相交的子集A1,A2, 元素个数分别是n1,n2, A1和A2中的元素之和分别是S1,S2。 设计一个尽可能高效的划分算法，满足|n1-n2|最小，且|S1-S2|最大，返回|S1-S2|的结果。 注意：函数头已经给出，只需要写出函数体。

函数接口定义：

int Partition(int a[],int n);  //  将数组a的整数集合划分成两个不相关子集，使得|n1-n2|最小，且|S1-S2|最大，返回|S1-S2|的结果。

裁判测试程序样例：

#include<stdio.h>int Partition(int a[],int n);int main(){    int a[60000],n;    scanf("%d",&n);    for(int i=0;i<n;i++)
    {        scanf("%d",&a[i]);
    }    printf("%d\n",Partition(a,n));
}int Partition(int a[],int n){/* 请在这里填写答案，仅写出函数体，不需要写函数头以及“{”，“ }”*/
 //划分整数数组算法}

输入样例：

在这里给出一组输入。例如：

6
1 9 20 8 100 15

输出样例：

在这里给出相应的输出。例如：

117

本题要求实现二分查找算法。

函数接口定义：

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。

裁判测试程序样例：

#include <stdio.h>#include <stdlib.h>#define MAXSIZE 10#define NotFound 0typedef int ElementType;typedef int Position;typedef struct LNode *List;struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */};List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */Position BinarySearch( List L, ElementType X );int main(){
    List L;
    ElementType X;
    Position P;

    L = ReadInput();    scanf("%d", &X);
    P = BinarySearch( L, X );    printf("%d\n", P);    return 0;
}/* 你的代码将被嵌在这里 */

输入样例1：

5
12 31 55 89 101
31

输出样例1：

2

输入样例2：

326 78 23331

输出样例2：

0

鸣谢宁波大学 Eyre-lemon-郎俊杰 同学修正原题！