练习1-1 二分查找

分数 20

作者 陈越

单位 浙江大学

查找算法中的“二分法”是这样定义的：给定 n 个从小到大排好序的整数序列 data，以及某待查找整数 x，我们的目标是找到 x 在 data 中的位置。
具体来说，不妨假设整数序列存储为一个序列 array，这个序列的结构定义在下面给出，数据存放在数组 data 中。若有 array->data[i] = x，则返回 i；否则返回失败标记 NotFound 表示没有找到。注意 C 语言数组下标从 0 开始。
二分法是先找到序列的中点 array->data[middle]，与 x 进行比较，若 array->data[middle] > x，则在左边的子序列中查找 x；若 array->data[middle] < x，则在右边的子序列中查找 x; 否则两者相等，则返回中点下标 middle。试用一个函数实现二分查找的功能，并分析最坏、最好情况下的时间、空间复杂度。

函数接口定义：

Position BinarySearch( ArrPtr array, ElemSet x );

其中ArrPtr结构定义如下：

typedef int Position;  /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等，要求可以通过 >、==、< 进行比较，并且题目保证传入的数据是递增有序的。

裁判测试程序样例：

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

#define kMaxSize 10
#define NotFound -1

typedef int ElemSet;
typedef int Position;  /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

Position BinarySearch( ArrPtr array, ElemSet x );

int main(void)
{
    int i, n;
    ArrPtr array;
    ElemSet x;
    
    array = (ArrPtr)malloc(sizeof(struct ArrNode));
    scanf("%d", &n);
    array->size = n;
    array->data = (int *)malloc(sizeof(int)*array->size); 
    for (i=0; i<n; i++) {
        scanf("%d", &array->data[i]);
    }
    scanf("%d", &x);
    printf("%d\n", BinarySearch(array, x));
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例 1：

5
12 31 55 89 101
31

输出样例 1：

1

输入样例 2：

3
26 78 233
31

输出样例 2：

-1

解答

Position BinarySearch( ArrPtr array, ElemSet x )
{
    int left = 0;
    int right = array->size - 1;
    int middle;  // 声明变量，不在此处计算

    while (left <= right)
    {
        middle = (left + right) / 2;  // 每次循环重新计算中间位置
        if (array->data[middle] == x)
        {
            return middle;  // 找到目标，返回下标
        }
        else if (array->data[middle] < x)
        {
            left = middle + 1;  // 目标在右半段，调整左边界
        }
        else 
        {
            right = middle - 1;  // 目标在左半段，调整右边界
        }
        // 移除此处的 return NotFound;，避免循环提前结束
    }
    
    // 循环结束仍未找到，返回未找到标记
    return NotFound;
}

注意

1.middle 要在循环内部赋值，每次循环middle都要变。

2.left 和 right都要跟middle有关，不是left += （left+right）/ 2 ，left 为 middle 加一， right 为 middle 减一。

实验1-1 有序数组的插入

实验1-1 有序数组的插入

分数 20

作者 陈越

单位 浙江大学

给定存储了 n 个从大到小排好序的整数，试将任一给定整数 x 插入数组中合适的位置，以保持结果依然有序。分析算法在最坏、最好情况下的时间、空间复杂度。
具体来说，不妨假设整数序列存储为一个序列 array，这个序列的结构定义在下面给出，数据存放在数组 data 中。因为数组长度是有限的，我们在此假设 data 数组的最大长度为 kMaxSize。如果在执行插入之前，数组已经满了，则插入失败，返回 false；如果待插入的元素 x 已经在 data 中，则不要重复插入，返回 false；如果插入成功，则返回 true。

函数接口定义：

bool DecrSeqInsert( ArrPtr array, ElemSet x );

其中ArrPtr结构定义如下：

typedef int Position;  /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等，要求可以通过 >、==、< 进行比较。这里题目保证传入的数据是递减有序的。

裁判测试程序样例：

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

#define kMaxSize 100
typedef enum { false, true } bool;

typedef int ElemSet;
typedef int Position;  /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

bool DecrSeqInsert( ArrPtr array, ElemSet x );

int main(void)
{
    int i, n;
    ArrPtr array;
    ElemSet x;
    
    array = (ArrPtr)malloc(sizeof(struct ArrNode));
    scanf("%d", &n);
    array->size = n;
    array->data = (int *)malloc(sizeof(int) * kMaxSize);
    for (i=0; i<n; i++) {
        scanf("%d", &array->data[i]);
    }
    scanf("%d", &x);
    if (DecrSeqInsert(array, x) == false) {
        printf("Insertion failed.\n");
    }
    printf("%d", array->data[0]);
    for (i=1; i<array->size; i++) {
        printf(" %d", array->data[i]);
    }
    printf("\n");
    printf("Array size = %d\n", array->size);
    
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例 1：

5
35 12 8 7 3
10

输出样例 1：

35 12 10 8 7 3
Array size = 6

输入样例 2：

6
35 12 10 8 7 3
8

输出样例 2：

Insertion failed.
35 12 10 8 7 3
Array size = 6

解答

bool DecrSeqInsert( ArrPtr array, ElemSet x )
{
    if (array->size >= kMaxSize)
    {
        return false;
    }
    int i , j , k;
    for (i = 0; i <array->size; i++)
    {
        if (x == array->data[i])
        {
            return false;
        }
    }
    for (j = 0; j < array->size; j++)
    {
        if (x > array->data[j])
        {
            break;
        }
    }
    for (k = array->size; k >j; k--)
    {
        array->data[k] = array->data[k-1];
    }
    array->data[j] = x;
    array->size++;

    return true;
}

注意

1.审题，题中如果数组满了或者有插入的数字，就返回 false 。

2.插入一个数，必须要么每个数向前挪，要么向后挪。