基础算法——二分法¶

二分查找的各种题型总结

https://www.cnblogs.com/grandyang/p/6854825.html 很好的总结，下面的题目也要做。

一些细节：如中间位置按照形式等价可以写成int middle = (left + right) / 2，这样可能存在溢出的问题，比如right是int类型的最大值，目标值恰好比最大值少1，第一次循环不会溢出，但是第二次循环就会溢出。利用位运算是加速考虑。

思考：容易出错的地方：初始边界怎么写，循环退出条件怎么写不容易出错？如果数组是降序排列的又该怎么办？

有序数组查找，按维数分为两大类，一维查找和二维查找，查找类型：

第一类：需查找和目标值完全相等的数¶

int binarySearch(vector<int>& nums, int target)
{
    int n = nums.size();
    if (n == 0 || target < nums[0] || target > nums.back()) return -1;
    int left = 0, right = n - 1;
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] == target) return middle;
        else if (nums[middle] < target) left = middle + 1;
        else right = middle - 1;
    }

    return -1;
}

可能的变形是数组的某部分顺序颠倒，更复杂就是存在重复元素。

典型应用：

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等

输入：第一行是case的个数n，接下来n行，每行第一个数是数组里元素的个数m，后面跟m个数

4
5 -3 -1 1 3 5 
1 0
2 0 2
2 -1 1

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int findEquall(vector<int> & nums) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] == middle) return middle;
        else if (middle < nums[middle]) right = middle - 1;
        else left = middle + 1;
    }

    return -1;       
}


int main()
{
    int tmp, caseNum, n;

    cin >> caseNum;
    while (caseNum--) {
        vector<int> nums;
        cin >> n;
        while (n--) {
            cin >> tmp;
            nums.push_back(tmp);  
        }
        cout << findEquall(nums) << endl;
    }

    return 0;
}

当然更完善的做法是考虑没找到的情况就返回-1。

标准库里有算法bool binary_search(v.begin(), v.end(), target)

第二类：查找第一个不小于目标值的数，可变形为查找最后一个小于目标值的数¶

类似于标准库的lower_bound()和upper_bound()

典型应用：

35.search insert position
34.find first and last position of element in sorted array（等价于找元素在数组内出现的次数或范围）
HDU 1257 最少拦截系统

//leetcode 35
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return left;
    }
};

查找最后一个小于目标值的数，只需要将找到第一个不小于目标值的位置向前移动一个位置即可。

第三类：查找第一个大于目标值的数，可变形为查找最后一个不大于目标值的数¶

典型题目：

leetcode 668 Kth Smallest Number in Multiplication Table
POJ 3579 Median（二分查找中位数）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target) left = mid + 1;
            else right = mid;
        }

        return left;
    }
};

第四类最大化最小值¶

《挑战程序设计竞赛》的例题，POJ 2456 Aggressive cows，让两头牛的最小间距是最大的，先排序，因为结果最小是0，最大不会超过最大元素与最小元素的差，所以可以用二分来去试探结果，但是有一个需要注意的点，如果按照上面的写法写出下面的程序，会出现死循环：

bool check(int d)
{
    int cnt = k - 1, pre = 0;
    for (int i = 1; i < n; ++i) {
        if (sequence[i] - sequence[pre] >= d) {
            --cnt;
            pre = i;
        }
        if (cnt == 0) break;
    }
    return cnt == 0;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> n >> k) {
        for (int i = 0; i < n; ++i) cin >> sequence[i];

        sort(sequence.begin(), sequence.begin() + n);
        int left = 0, right = sequence[n - 1] - sequence[0];

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(mid)) left = mid;
            else right = mid - 1;
        }
        cout << left << endl;
   }

    return 0;
}

问题出现在mid的求法，考虑lower_bound的时候，如果最后剩下两个元素，那么满足条件left = mid + 1会使left = right退出循环，upper_bound同理，但是本题，满足条件时候left不改变，比如最后left = 2, right = 3，mid会等于2，如果2一直满足条件，就会造成死循环，也就是说，最后剩下两个元素，要保证满足判断条件的时候，left的数值是增加的，那么就需要去修改mid的求法，所以应该为mid = int mid = left + ((right - left + 1) >> 1);。

正确解答：

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

int n = 100005, k;
vector<int> sequence(n);

// bool check(int d)
// {
//  int last = 0;
//  for (int i = 1; i < k; ++i) {
//      int cur = last + 1;
//      while (cur < n && sequence[cur] - sequence[last] < d) ++cur;
//      if (cur == n) return false;
//      else last = cur;
//  }

//  return true;
// }

bool check(int d)
{
    int cnt = k - 1, pre = 0;
    for (int i = 1; i < n; ++i) {
        if (sequence[i] - sequence[pre] >= d) {
            --cnt;
            pre = i;
        }
        if (cnt == 0) break;
    }
    return cnt == 0;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> n >> k) {
        for (int i = 0; i < n; ++i) cin >> sequence[i];

        sort(sequence.begin(), sequence.begin() + n);
        int left = 0, right = sequence[n - 1] - sequence[0];

        while (left < right) {
            int mid = left + ((right - left + 1) >> 1);
            if (check(mid)) left = mid;
            else right = mid - 1;
        }
        cout << left << endl;
   }

    return 0;
}

第五类最小化最大值¶

典型题目：

POJ 3273 Monthly Expense

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

int n = 100005, k;
vector<int> sequence(n);

bool check(int d)
{
    int cnt = k - 1;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        //在财务月内的和小于d
        if (sum + sequence[i] <= d) {
            sum += sequence[i];
        }
        else {
            --cnt; //开启一个新的财务月
            sum = 0;
            --i;
        }

        if (cnt < 0) break; //cnt < 0说明财务月的预算偏小
    }

    return cnt < 0;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (cin >> n >> k) {
        for (int i = 0; i < n; ++i) cin >> sequence[i];

        int left = 0, right = INF;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(mid)) left = mid + 1;
            else right = mid;
        }
        cout << left << endl;
   }

    return 0;
}

二分优化LIS和LCS¶

利用二分法来将 $O(n^2)$ 的动态规划的方法优化到 $O(n \log n)$ 。

详细在《动态规划-最长公共子序列(LCS)》和《动态规划-最长上升子序列（LIS）》

常用函数`ceil`和`floor`¶

包含在头文件<cmath>里，ceil是向上取整，floor是向下取整。

在POJ 3104 Drying 里面使用了ceil()函数。

floor函数的另一个典型用法是保留特定位数的浮点数，并四舍五入，比如一个浮点数d，要保留小数点后4位：

floor(d * 10000.0 + 0.5) / 10000.0;

基础算法——二分法¶

第一类： 需查找和目标值完全相等的数¶

第二类： 查找第一个不小于目标值的数，可变形为查找最后一个小于目标值的数¶

第三类： 查找第一个大于目标值的数，可变形为查找最后一个不大于目标值的数¶

第四类 最大化最小值¶

第五类 最小化最大值¶