【挑战程序设计竞赛】 二分搜索

发表于

最近看了许多的算法内容都和这个东西有关，从最开始的编程题求峰值，到中间选取任意个数等于一个固定值问题，将二分法与链表结合，有了二叉查找树，红黑数等等。

来看一个题目：从一个装有n张卡片的口袋里面有放回的选取4张卡片，给定一个值m，判断存在这4张卡片的总和为m。
样例输入1:

1
2
3
3
1 ,2 ,3
4

这种情况答案应该是存在和为4的，比如1，1，1，1。

样例输入2:

1
2
3
3
4 ,2 ,3
4

显然这种情况不存在总和为4的情况。

解决这个问题最简单的方法就是暴力枚举，O(N^4)。
暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool selok(vector<int> nums, int m) {
    int len = nums.size();
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            for (int k = 0; k < len; k++) {
                for (int ind = 0; ind < len; ind++) {
                    if (nums[i] + nums[j] + nums[k] + nums[ind] == m) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

二分搜索1个变量
时间复杂度O(N^3*log2(N))

1
2
3
4
5
6
7
8
9
10
11
12
bool selok2(vector<int> nums, int m) {
    int len = nums.size();
    sort(nums.begin(), nums.end());
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            for (int k = 0; k < len; k++) {
                if (binsearch(nums, m - nums[i] - nums[j] - nums[k])) { return true; }
            }
        }
    }
    return false;
}

二分搜索两个变量
时间复杂度O(N^2*log2(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool selok3(vector<int> nums, int m) {
    int len = nums.size();
    vector<int> nums_sum;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            nums_sum.push_back(nums[i] + nums[j]);
        }
    }
    sort(nums_sum.begin(), nums_sum.end());
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (binsearch(nums_sum, m - nums[i] - nums[j])) { return true; }
        }
    }
    return false;
}

二分法

1
2
3
4
5
6
7
8
9
10
11
bool binsearch(vector<int>&nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) { return true; }
        else if (nums[mid] < target) { left = mid + 1; }
        else { right = mid - 1; }
    }
    return false;
}

notes:二分法边界控制有点麻烦，要小心。比如(left+right)/2没有left+(right-left)/2好，前者可能会溢出。参考文章