算法分析与设计技巧（开篇绪论）

由于《算法设计技巧与分析》沙特M.H.Alsuwaiyel著中国工信出版集团 一书中的代码都是伪代码，这里我想借自己绵薄之力用c++实现一下。

先来看看求和公式（图片来源于知乎，百度百科和360百科）：

平方和公式
等差数列求和公式 等比数列求和公式.png

接着我们来看看1-2 binarySearch二分搜索。

//传入一个有序数组,x 为要寻找的目标值
int binarySearch(const int* a,int n, int x){
    int low = 0, high = n - 1, j = -1;
    while(low <= high && j == -1){
        int mid = (low + high) / 2;
        if(a[mid] == x)
            j = mid;
        else if (x < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return j;
}

我们可以写个例子测试一下

int main(){
    //写个例子测试一下
    int a[] = {1,10,20,30,40,50,60,70,80,90,100};
    int number = sizeof(a) / sizeof(int);
    int x = 101;//试试其他值...
    int result = binarySearch(a, number, x);
    if(result != -1)
        cout << "找到了，在索引 " << result << endl;
    else
        cout << "没找到" << endl;
    return 0;
}

定理1.1: 对于一个大小为n的排序数组，算法binarySearch执行比较的最大次数为

这里我们多事一点，我们看到P32的1.15练习的1.1题。

令A[1...60] = 11,12,...,70,用二分算法搜索下列x值时执行了多少次比较运算？
(a) 33 (b) 7 (c) 70 (d) 77

我们这里用程序跑一下它,由于它是从1开始的，我们这里也改一下程序。把数组A从1开始。

int binarySearchCountTime(const int *a, int n, int x) {
    int low = 1, high = n, j = -1;
    int time = 0;
    while (low <= high && j == -1) {
        int mid = (low + high) / 2;
        if (a[mid] == x)
            j = mid;
        else if (x < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
        time++;
    }
    cout << "比较次数" << time << endl;
    return j;
}

主函数

int main() {
    //写个例子测试一下
    int a[61];
    for (int i = 0; i <= 60; i++)
        a[i] = i + 10;
    int number = 60;
    int target[4] = {33, 7, 70, 77};
    for (int i : target) {
        binarySearchCountTime(a, number, i);
    }
    return 0;
}

运行结果


合并两个有序小序列：

//执行后a升序排列，数组b为辅助数组
void merge(int *a, int *b, int p, int q, int r) {
    int s = p, t = q + 1, k = p;
    while (s <= q && t <= r) {
        if (a[s] <= a[t])
            b[k++] = a[s++];
        else
            b[k++] = a[t++];
    }
    if (s == q + 1)
        for (int i = t; i <= r; i++)
            b[k++] = a[i];
    else
        for (int i = s; i <= q; i++)
            b[k++] = a[i];
    for (int i = p; i <= r; i++)
        a[i] = b[i];
}

记得小序列是有序的。写个测试

int main() {
    int a[8] = {1627, 1896,3147,3605,2957,3000,3592,3959};
    int b[8] = {0};

    merge(a, b, 0, 3, 7);

    for (int i : a)
        cout << i << " ";
}

输出：

1627 1896 2957 3000 3147 3592 3605 3959