2.11

Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integers A1 < A2 < A3 < … < AN. What is the running time of your algorithm?

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>

//2.11

//By using Binary Search
int SearchArry(int head, int tail, int *arr, int key) {
    int mid = (head + tail) / 2;
    if (head > tail) {
        return -1;
    }
    if (arr[mid] == key) {
        return 1;
    }
    else if (arr[mid] > key) {
        return SearchArry(head, mid - 1, arr, key);
    }
    else {
        return SearchArry(mid + 1, tail, arr, key);
    }
}


int main() {
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int B[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10};
    int C[] = {1, 5, 6, 7, 10, 12, 13, 15, 17, 20};
    int D[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int E[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

    int aim = 7;
    printf("A: %d\n", SearchArry(0, 9, A, aim));
    printf("B: %d\n", SearchArry(0, 9, B, aim));
    printf("C: %d\n", SearchArry(0, 9, C, aim));
    printf("D: %d\n", SearchArry(0, 9, D, aim));
    printf("E: %d\n", SearchArry(0, 9, E, aim));
    return 0;
}

output

1
2
3
4
5
A: 1
B: -1
C: 1
D: 1
E: -1

TimeAnalysis

在递归中，每次操作为常数时间，递归次数按下式估算：
设数组长度为A，每次（k）递归长度减半，长度为1时停止递归，则有

A∗(1/2)k=1k=log2AA*(1/2)^k =1\\k=log_2A

所以时间复杂度为

O(logN)O(logN)

2.12(a)

Give efficient algorithms (along with running time analysis) to: Find the minimum subsequence sum.

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>

//2.11
//finding min subsequences
//By using the divide and conquer method
int MinSubsequence(int *arr, int head, int tail) {
    //end condition
    if (head == tail) {
        return arr[head];
    }
    int mid = (head + tail) / 2;
    //left min
    int leftMin = MinSubsequence(arr, head, mid);
    //right min
    int rightMin = MinSubsequence(arr, mid + 1, tail);
    //cross min
    int cLmin = 1000000;
    int cRmin = 1000000;
    int tempSum = 0;
    for (int p = mid; p >= head; p--) {
        tempSum += arr[p];
        if (tempSum < cLmin) {
            cLmin = tempSum;
        }
    }
    tempSum = 0;
    for (int p = mid + 1; p <= tail; p++) {
        tempSum += arr[p];
        if (tempSum < cRmin) {
            cRmin = tempSum;
        }
    }
    //return min
    if (leftMin <= rightMin && leftMin <= cLmin + cRmin) {
        return leftMin;
    }
    else if (rightMin <= leftMin && rightMin <= cLmin + cRmin) {
        return rightMin;
    }
    else {
        return cLmin + cRmin;
    }

}


int main() {
    int A[] = {-43, 45, 5, -46, 20, 4, 43, -16, 41, 31, -28, -38, 4, 14, -49};
    int B[] = {16, -33, 40, -17, 40, 36, 40, 9, -14, 23, -40, 11, -10, -25, -28};
    int C[] = {46, -39, -14, 12, 8, -7, 25, -47, 36, 26, 28, 17, -41, 14, 47};
    int D[] = {-3, 35, 6, 47, 7, -45, -34, -37, -26, -25, -4, -23, 38, -20, 24};
    int E[] = {-48, -40, -4, -4, -42, -35, -8, 39, -36, -39, -43, 42, 23, 37, -4};

    printf("A: %d\n", MinSubsequence(A, 0, 14));
    printf("B: %d\n", MinSubsequence(B, 0, 14));
    printf("C: %d\n", MinSubsequence(C, 0, 14));
    printf("D: %d\n", MinSubsequence(D, 0, 14));
    printf("E: %d\n", MinSubsequence(E, 0, 14));

    return 0;
}

output

1
2
3
4
5
A: -97
B: -92
C: -62
D: -194
E: -260

TimeAnalysis

同上题，每次递归中时间复杂度为O(N)[循环]，递归次数同为log(N)
所以时间复杂度为

O(NlogN)O(NlogN)