刷题时总是写了又忘，所以专门整理了一个题目记录本。

刷题记录本

做到 二分算法 的专题时，对于其边界的处理非常棘手。所以写了这篇博客对二分的实现、应用进行一个全面的总结。

标准二分

int binarySearch(Element array[], int len, int key){
    int low = 0, high = len - 1, middle;
    while(low <= high){
        middle = (low + high) / 2;
        if(array[middle] == key){  //找到,返回下标索引值
            return middle;
        }else if(array[middle] > key){  //查找值在低半区
            high = middle - 1;
        }else{  //查找值在高半区
            low = middle + 1;
        }
    }
    return -1;  //找不到
}

说实话 这样做扩展性不好，不推荐这么写

扩展性强的 二分

按照 std upper_bound lower_bound 库的效果设计的二分函数

mylower_bound

寻找数组中 第一个大于等于 目标值的 下标

// last 初始值 = size时 target超出上限范围会返回 end下标
int mylower_bound(int* array ,int size,int key){
	int first = 0, middle ,last = size-1;
	while(first<last){
		middle = (first+last) >> 1;
		if(array[middle] < key ) //当middle小于要找的位置 ， first +1 也不会超过key的位置，最多相同
			 first = middle + 1;
 		else
			last = middle ; //middle有可能等于要找的位置 ， last = middle ， 用first不断逼近
		
	}
	return first;
}

myupper_bound

寻找数组中 第一个大于 目标值的 下标

// last 初始值 = size 时  target超出上限范围会返回 end下标
int myupper_bound(int* array ,int size,int key){
	int first = 0, middle ,last = size-1;
	while(first<last){
		middle = (first+last) >> 1;
		if(array[middle] <= key ) //此时的middle一定大于要找的位置。用first不断逼近
			first = middle +1; //当middle等于要找的位置， 我们记录first = middle+1
		else
			last = middle ;
		
	}
	return first;
}

实际使用

35.搜索插入位置

// 这个标准二分的改版 等价求出 lower_bound 写法风格不同，效果一样的
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(nums[mid] < target)
                l = mid+1;
            else 
                r = mid-1;
        }
        return l;
    }
};

std库函数 自定义

引入头文件 #include <algorithm> 即可使用

以下面的实际使用举例 说明 库函数的使用方法

注意自定义 比较函数 两者的区别 ，使用 upper_bound lower_bound

对于同一参数 是不需要修改比较函数的，都是 return i < j;

#include <iostream>     // std::cout
#include <algorithm>    // std::upper_bound
#include <vector>       // std::vector
using namespace std;

//以普通函数的方式定义查找规则 等价operator
bool mycomp(int i, int j) { return i > j; }
auto mycomp1 = [](int i, int j)->bool { return i > j; };

class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i<j;
    }
};

int main() {
	int x = 1;
    int a[5] = {3,7,9,12,15};
    // 若是输入指针则 注意不能超出数组有效范围 没有那个end属性 查找大于数组最大值时返回的也是最后一个元素的指针
    // 返回值是对应元素的下标或迭代器 找不到对应值时会返回 vector.end() 
    int *p = upper_bound(a, a + 4, x);
    cout << "*p = " << *p << endl;
    p = lower_bound(a, a + 4, x);
    cout << "*p = " << *p << endl;

    // 以函数对象的形式定义查找规则 j为容器遍历值 i为输入的查找值
    // low是找出大于等于指定值，即找出i>=j才停 i是遍历值 函数内不成立跳出循环
	vector<int> myvector{ 1,2,3,4,5 };
    vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), x, mycomp2());
    if(iter==myvector.end())
    	cout << "error"<<endl;
    else
    	cout << "*iter = " << *iter;


    // uper找出大于指定值，即找出j>i才停 j是遍历值 函数内成立跳出循环
    // 以函数对象的形式定义查找规则 i为容器遍历值 j为输入的查找值
    vector<int>::iterator iter1 = upper_bound(myvector.begin(), myvector.end(), x, mycomp2());
    if(iter1==myvector.end())
    	cout << "error"<<endl;
    else
    	cout << "*iter1 = " << *iter1;
    return 0;
}

二维容器 注意点:

int target = 1;
vector<vector<int>> myvector{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
//第二个形参不设const会报错
auto row = [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}; 
//目标值一定要与遍历元素类型相同，此处目标值转为 一维容器
vector<vector<int>>::iterator iter = lower_bound(myvector.begin(), myvector.end(), vector<int>{target}, row);

练习

74.搜索二维矩阵

class Solution {
public:
    // 以第一列即行首为目标二分 后对该行进行列二分
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto row = [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];};
        // 注意第二个形参一定要 const 建议全部写成const, 第三个比较参数的类型要与前面容器元素类型一致 即target 要从int -> vector
        auto it = upper_bound(matrix.begin(), matrix.end(), vector<int>{target}, row);
        int index = distance(matrix.begin(), it); // 以行首二分 寻找第一个大于 target 值  没找到返回的it为end
        index--;
        if(index < 0)
            return false;
        auto it1 = lower_bound(matrix[index].begin(), matrix[index].end(), target); // 对该行进行列的二分查找
        return it1 != matrix[index].end() && *it1 == target;
    }
};

240.搜索二维矩阵II

// 74题进阶，由题意 任意坐标右下方 全部大于等于该坐标值 左上方全部小于等于该值 时间复杂度O(logm + logn)
// 所以先对第一行列二分删除多余大于target的列 再行二分删除小于target的行 不断迭代下去
class Solution {
public:
    int myupper_bound(vector<vector<int>>& matrix, int row, int column, int target) {
        int L = 0, R = column + 1;
        while (L < R) {
            int mid = (L + R) >> 1;
            if(matrix[row][mid] <= target)
                L = mid+1;
            else
                R = mid;
        }
        return L;
    }
    int mylower_bound(vector<vector<int>>& matrix, int row, int column, int target) {
        int L = row, R = matrix.size();
        while (L < R) {
            int mid = (L + R) >> 1;
            if(matrix[mid][column] < target)
                L = mid+1;
            else
                R = mid;
        }
        return L;
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 有效范围 行为 row->matrix.end()-1 列为 0-cloumn
        int row = 0, column = matrix[0].size()-1; 
        while (1) {
            // std库做法
            // auto it = upper_bound(matrix[row].begin(), matrix[row].begin()+column+1, target);
            // if(it == matrix[row].begin())
            //     break;
            // column = distance(matrix[row].begin(), it) - 1; // column 右边删去
            column = myupper_bound(matrix, row, column, target) - 1; // column 右边删去
            if(column < 0) //target 比范围内最小值还小
                break;
            row = mylower_bound(matrix, row, column, target);
            if(row == matrix.size()) //target 比范围内最大值还大
                break;
            if(matrix[row][column] == target)
                return true;
        }
        return false;
    }
};

410.分割数组的最大值

class Solution {
public:
    // 二分法 绝了
    bool isok(vector<int>& nums, int mid, int m) {
        int count = 1, temp = 0;
        for(auto num : nums) {
            if ( temp + num <= mid) 
                temp += num;
            else {
                temp = num;
                count ++;
            }
        }
        return count > m;
    }
    int splitArray(vector<int>& nums, int m) {
        int L = -1,R = 0, mid;
        // L为整个数组的最大值 R为整个数组的总和 分割的子数组和的最大值 取值范围即在L R之中
        // 由于分割次数 m 和 分割子数组和的最大值 成线性负相关 关系 所以可以采用二分的方法 靠近测试
        for (auto num : nums) {
            L = max(L, num);
            R += num;
        }
        while(L < R) {
            mid = (L + R)/2;
            if(isok(nums, mid, m))
                L = mid+1;
            else 
                R = mid;
        }
        return L;   // L==R
    }
};