begin到first的区间[begin, first)是否对于一个特性是单调的？last到end的区间[last,end)是否针对一个特性是单调的？
是否已知区间的范围？如果不知道，是否可以用单边二分查找来先确定范围？

二分查找三基础：
LC35 Search Insert Position
LC704 Binary Seach
LC34 Find First and Last Position of Element in Sorted Array
[equal_range —> 将 lower_bound中的!(*mid < target)分解为小于：target < *mid 和等价：!(*mid < target) && !(*mid > target)，将等价的区间分为[first, mid)和[mid, last)，再在前面做lower_bound后面做upper_bound。
简单二分查找：
LC278 第一个错误的版本单边二分。注意下标溢出。记录上一次badVersion的位置，缩小二分区间。
剑指53 - II 0到n-1中缺失的数字
⚠️LC1060 有序数组上缺失的数字 [设计一个函数计算到目前为止缺失的元素个数，记得要找lower_bound前一个元素（最后一个不大于）]
剑指53 - III 数组中数值和下标相等的元素[小心size_t和int的大小比较]

峰值数组：
LC1095 山脉数组中查找目标值
 LC162 寻找峰值

旋转数组：
LC153 Find Minimum in Rotated Sorted Array
LC154 Find Minimum in Rotated Sorted Array II [有重复数字，遇到重复直接线性查找]
LC33 Search in Rotated Sorted Array [想要在旋转数组上找某个数字]
矩阵查询：
LC74 Search a 2D Matrix [展开为一维/两次二分/线性]
LC240 Search a 2D Matrix II [线性/对角线二分]
困难二分查找：
⚠️LC4 排序数组的中位数
⚠️LC410 分割数组的最大值
⚠️LC162 寻找峰值
 LC222 完全二叉树的节点个数
数学二分：
LC96 Sqrt(x)
LC878 第N个神奇数字

基础知识

二分查找的基本思路就是维护两个循环不变式，直到搜索空间变为空。

求区间中点

不能直接使用 mid = (first + last) / 2，因为first + last的结果可能溢出。
在区间长度为偶数的时候，存在两个可能的区间中点
Mid1 = first + (last - first) / 2;
Mid2 = first + (last - first - 1) / 2;

一般我们用Mid1，因为不需要额外-1.

比较符号

按照C++ STL的惯例，只使用operator<()来做比较。

STL中相等(equality)和等价(equivalence)的区别

相等：a == b
等价：!(a < b) && !(b < a)

更多关于STL中【相等】和【等价】的区别，可以参考 Effective STL, Scott Meyers, Item19: Understand the difference between equality and equivalence

实现`lower_bound` 和 `upper_bound`

LC35 Search Insert Position

[first, last) 左闭右开区间表示法

lower_bound维护下面的循环不变式：

[begin, first) 中的所有元素小于 target.
[last , end ) 中的所有元素不小于 target.
[first, last ) 区间长度大于0.

适用于迭代器为RandomAccessIterator的Container的lower_bound

code

template<typename RandomAccessIterator, typename T>
RandomAccessIterator lower_bound(RandomAccessIterator first, RandomAccessIterator last, const T& target){
	while(first < last){
		auto middle = first + distance(first, last) / 2;
		if(*middle < target) first = middle + 1;
		else                 last  = middle; 
        //这里绝对不可以是else if(target < *middle)，否则当target == *middle的时候，不符合任意条件，导致死循环。
	}
	return first;
}

upper_bound维护下面的循环不变式：

target 不小于 [begin, first) 中的所有元素.
target 小于 [last , end ) 中的所有元素.
[first, last ) 区间长度大于0.

适用于迭代器为RandomAccessIterator的Container的lower_bound

code

template<typename RandomAccessIterator, typename T>
RandomAccessIterator upper_bound(RandomAccessIterator first, RandomAccessIterator last, const T& target){
	while(first < last){
		auto middle = first + distance(first, last) / 2;
		if(target < *middle) last   = middle;
		else                 first  = middle + 1; 
        //这里绝对不可以是else if(target < *middle)，否则当target == *middle的时候，不符合任意条件，导致死循环。
	}
	return first;
}

实现`binary_seach`

通过`lower_bound`实现`binary_seach`

LC704 Binary Seach

C++ STL是用过调用lower_bound来实现的。因为lower_bound的返回值it是第一个【不小于（大于等于）】target的iterator，即!(*it < target)所以如果想要测试it是否和target等价，需要加上条件：

it != nums.end()
!(target < *it)

即 it非尾迭代器且!(target < *it) && !(*it < target)(STL的等价(equivalent)).

code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto it = my_lower_bound(nums.begin(), nums.end(), target);
        if(it != nums.end() && !(target < *it) )
            return static_cast<int>(distance(nums.begin(), it));
        return -1;
    }
    
    template<typename RandomAccessIterator, typename T>
    RandomAccessIterator my_lower_bound(RandomAccessIterator first, RandomAccessIterator last, const T& target){
        while(first < last){
            auto middle = first + distance(first, last) / 2;
            if(*middle < target) first = middle + 1;
            else                 last  = middle;
        }
        return first;
    }
};

实现`equal_range`

equal_range维护下面的循环不变式：

target 小于 [last, end) 中的所有元素.
[begin, first) 中的所有元素小于 target.
[first, last ) 区间长度大于0.

适用于迭代器为RandomAccessIterator的Container的equal_range

code

tempalte<typename RandomAccessIterator, typename T>
pair<RandomAccessIterator, RandomAccessIterator> equal_range(RandomAccessIterator first, RandomAccessIterator last, const T& target){
	while(first < last){
		auto middle = first + distance(first, last) / 2;
		if     (*middle < target)  first = middle + 1;
		else if(target < *middle)  last  = middle; 
		else // (!(*middle < target) && !(target < *middle)) ==> equivalent
		{
			it1 = lower_bound(first , middle, target);
			it2 = upper_bound(middle,   last, target);
			return {it1, it2};
		}
	}
	return {it1, it2};
}

LC34 Find First and Last Position of Element in Sorted Array的解：

code

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto [it1, it2] = my_equal_range(nums.begin(), nums.end(), target);
        // 注意这里仍然需要像binary_search一样判断一下等价条件
        if(it1 != nums.end() && !(target < *it1)) 
            return {static_cast<int>(distance(nums.begin(), it1))
                    ,static_cast<int>(distance(nums.begin(), it2)) - 1};
        else return {-1, -1};
    }
    template<typename RandomAccessIterator, typename T>
    pair<RandomAccessIterator, RandomAccessIterator> my_equal_range(RandomAccessIterator first, RandomAccessIterator last, const T& target){
        while(first < last){
            auto middle = first + distance(first, last) / 2;
            if     (*middle < target)  first = middle + 1;
            else if(target < *middle)  last  = middle; 
            else // (!(*middle < target) && !(target < *middle)) ==> equivalent
            {
                auto it1 = lower_bound(first , middle, target);
                auto it2 = upper_bound(middle,   last, target);
                return {it1, it2};
            }
	    }
	    return {first, last};
    }
};

简单二分查找

单侧二分查找

有一个前面全是0，后面全是1的数组。我们想要找到这个数组的转折点。如果我们知道数组元素个数n，我们可以在这个区间上做二分查找。如果我们不知道元素个数n，我们可以逐步扩大区间(A[1],A[2],A[4],A[8],$\cdots$)，直到找到非零值位置，然后在这个区间上做二分查找。
LC278 第一个错误的版本
需要注意的问题：

- 单边二分查找可能会增长超过INT_MAX。如果发现要溢出了，就直接给i = INT_MAX即可。
- 我们在做单边二分查找的时候，可以记录一下上一次仍不是BadVersion的index，这样可以缩小之后的二分查找范围。

code

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        // to use binary_search
        // we have to find a bad version
        int i = 1;
        int first = 1;
        while(!isBadVersion(i))
        {
            first = i;
            if(i < INT_MAX / 2)
                i *= 2;
            else
                i = INT_MAX;
        }
        //now we can use binary search
        int last  = i;
        while(first < last)
        {
            int mid = first + (last - first) / 2;
            if(!isBadVersion(mid)) first = mid + 1;
            else                   last  = mid;
        }

        return first;
    }
};

有序数组上的次数统计

有序数组上缺失的数字

剑指53 0到n-1中缺失的数字

维护以下的循环不变式

[begin, first) 中，具有下标i的所有元素都满足nums[i] == i
[last, end ) 中，具有下表j的所有元素都满足nums[j] != j
first < last

code

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if(nums.empty()) return 0;
        size_t first = 0;
        size_t last  = nums.size();
        
        while(first < last){
            size_t mid = first + (last - first) / 2;
            if(nums[mid] == mid) first = mid + 1;
            else                 last  = mid;
        }
        return first;
    }
};

LC1060 有序数组上缺失的数字

更为复杂版本的数组上缺失的数字，这里没有要求所有数字的范围是0 到 (n - 1)，而是随意的一个范围。

给出一个有序数组 A，数组中的每个数字都是独一无二的，找出从数组最左边开始的第 K 个缺失数字。

思路：

我们需要知道到数字中每一元素为止，缺失了多少个元素
- 比如 nums = [4, 7, 9, 10] 这个数组，到7缺失了2个(5,6)，到9缺失了3个(5,6,8)，到10也是缺失了3个(5, 6, 8)。纸笔演算一下就可以发现，设这个元素的迭代器为it, 这个缺失数应该是：
  *it - *nums.begin() - distance(nums.begin(), it)
- 也可以用[4,7,9,10]减去[4,5,6,7]就是到每个元素为止缺失元素的个数。
知道了到每个元素为止缺了多少元素，那我们只要找到k的lower_bound，即第一个缺失元素不小于k的元素，他前面那个元素(设before为他的迭代器)就最后一个缺失元素小于k的。
我们只需要计算 (k - 到before为止缺失元素的个数) + *before，就是第k个缺失的元素了

code

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {

        // use lower bound to find the first element
        // that has missingElementsUntil that is not less than k
        auto first = nums.begin();
        auto last  = nums.end();
        while(first < last)
        {
            auto mid = first + distance(first, last) / 2;
            if (missingElementsUntil(nums.begin(), mid) < k) 
                first = mid + 1;
            else
                last  = mid; 
        }
        // decrease first by 1 --> the last element that has                 // missingElementUnitl less than k
        
        --first;

        // the missing element is
        // k - missingElementsUntil(first) + *first

        return k - missingElementsUntil(nums.begin(), first) + *first;
    }
    template<typename It>
    int missingElementsUntil(It begin, It it)
    {
        return *it - *begin - distance(begin, it);
    }
};

数组中数值和下标相等的元素

剑指53 - III 数组中数值和下标相等的元素

设一个元素的下标为i, 注意到：

如果nums[i] < i，因为数组是单调递增的，且没有重复元素，对于i之前下标为j的任意元素，都有nums[j] < j
对于i < nums[i]，类似的结论也成立。

维护下面的循环不变式

[begin, first)，对于任意的下标i的元素都满足nums[i] < i
[last, end )，对于任意的下标i的元素都满足i < nums[i]
first < last

注意：一个size_t类型的变量和int类型变量比较大小的时候，一定要强制类型转换后再比较

code

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        size_t first = 0;
        size_t last  = nums.size();
        while(first < last){
            size_t mid = first + (last - first) / 2;
            if(nums[mid] < static_cast<int>(mid)) //这里的强制类型转换不可少
                first = mid + 1;
            else if(static_cast<int>(mid) < nums[mid]) //这里的强制类型转换不可少
                last = mid;
            else                     
                return mid;
        }
        return -1;
    }
};

旋转数组

LC153 Find Minimum in Rotated Sorted Array：不含重复元素
LC154 Find Minimum in Rotated Sorted Array II：含有重复元素
[LC33 Search in Rotated Sorted Array]：查找指定元素
剑指Offer 11

思路：

一个有序数组被旋转后，第一个元素必然大于最后一个元素：(1,2,3,4,5) —> (4,5,1,2,3)
旋转后的数组可以被分成递增的两部分(4,5)和(1,2,3)
旋转后的数组最小值出现在第二部分的头
大于等于旋转后数组的头的数字，必然比旋转后数组的尾大，因此不属于第二部分 —> 第一部分的数字都大于等于旋转后数组的头
小于等于旋转后数组的尾的数字，必然比旋转后数组的头小，因此不属于第一部分 —> 第二部分的数字都小于等于旋转后数组的尾
每一部分都是单调的 —> 可以采用二分查找

当没有重复数字时，维护下面的循环不变式

- [begin, first) 为前递增数组的元素
- [last,  end  ) 为后递增数组的元素
- 1 < last - first

我们要找的最小值就是迭代结束后的*last。这里需要注意一个边界条件：如果数组只有一个数，会导致last变成尾后迭代器。

code

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums.front();
        if(nums.front() < nums.back()) return nums.front();

        auto first = nums.begin();
        auto last  = nums.end();

        while(first < last)
        {
            auto mid = first + distance(first, last) / 2;
            // if mid is greater than or equal nums.front()
            // then mid belongs to the first part 
            if(!(*mid < nums.front())) first = mid + 1;
            else                       last  = mid;
        }

        // what we want is the beginning of the second 
        // part, that is last
        return *last;
    }
};

当数组中包含重复数字时，如果我们如果发现*mid和头尾的元素相等，我们就无法再通过二分查找找到最小值了。因为这些相等的元素可以被任意分配第一部分和第二部分。直接采用线性搜索即可。

code

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.size() == 1 || nums.front() < nums.back()) 
            return nums.front();
        auto first = nums.begin();
        auto last  = nums.end();
        while(first < last)
        {
            auto mid = first + distance(first, last) / 2;
            // this time we have duplicate elements in the array
            // if mid is equal to the front or back
            // we cannot get any information from that
            if(*mid > nums.front()) first = mid + 1;
            if(*mid < nums.back())  last  = mid;
            else //equal situation, we have to use linear search.
            {
                return *min_element(nums.begin(), nums.end());
            }
        }
        
        return *last;
    }
};

LC33 Search in Rotated Sorted Array

先找到第二区间的头，然后根据target和nums.front()的关系决定它在哪一个区间上。之后在那个区间上再做一次二分查找。

code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        auto minIt = lower_bound(nums.begin(), nums.end(), nums.front(), greater_equal<int>{});
        // if target belongs to the first range
        if(target >= nums.front())
        {
            auto tarIt = lower_bound(nums.begin(), minIt, target);
            return tarIt != minIt && *tarIt == target ? 
                   tarIt - nums.begin() : 
                   -1;
        }
        else
        {
            auto tarIt = lower_bound(minIt, nums.end(), target);
            return tarIt != nums.end() && *tarIt == target ?
                   tarIt - nums.begin():
                   -1;
        }
    }
};

峰值数组

峰值数组和旋转数组的差别在于：峰值数组的山峰一侧是递增的，另一侧是递减的。而旋转数组的最小值左右两边的数组都是递增的。

LC162 寻找峰值

思路一：
该数组中可能有多个峰值。但仍然可以用二分查找来寻找峰值[为什么？]。

code

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        auto first = nums.begin();
        auto last  = --nums.end();

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if (*mid < *(mid + 1)) first = mid + 1;
            else                   last  = mid;
        }

        return distance(nums.begin(), last);
    }
};

思路二：
设这个数组为$a$，数组中的元素为$an$，$a{n} \neq a{n+1}$，我们认为$a{-1} = a_{end + 1} = -\infty$ 不加证明的给出以下结论：

如果$an < a{n+1}$，那么峰值在[n + 1, end)中
如果$an > a{n+1}$，那么峰值在[begin, n+1)$中

这正好对应了二分查找的两个区间的特点。

维护以下的循环不变式：

[begin, first)区间中的值不是峰值
[last, end]区间中的值不是峰值
first < last

注意：

- 不能将last初始化为尾后迭代器，因为`mid`可能会被移动到最后一个元素的位置。在比较`mid`和`mid+1`的时候会导致解引用尾后迭代器。
- 如果想把last初始化成尾后迭代器，也可以在解引用`mid + 1`之前加一个判断，看看是不是`end`

code

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        auto first = nums.begin();
        auto last  = --nums.end();

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if (*mid < *(mid + 1)) first = mid + 1;
            else                   last  = mid;
        }

        return distance(nums.begin(), last);
    }
};

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        auto first = nums.begin();
        auto last  = nums.end();

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if (mid + 1 != nums.end() && *mid < *(mid + 1)) 
                first = mid + 1;
            else                   
                last  = mid;
        }

        return last - nums.begin();
    }
};

LC1095 山脉数组中查找目标值

首先找到峰值，之后用峰值将数组分割为递增和递减的两部分。在这两部分上分别用二分查找即可。
山脉数组中只有一个峰值，我们可以通过二分查找来找到峰值。

[begin, first)之间的元素都属于递增区间
[last, end)之间的元素都属于递减区间
判断条件：如果mid == 0(第一个元素) 或 m.get(mid - 1) < m.get(mid)(比左边的元素大)，则mid必然处于递增区间。否则mid处于递减区间。据此更新first和last的位置。

code

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */


auto peak(MountainArray& m) -> size_t
{
    auto begin = 0;
    auto end = m.length();
    auto first = 0;
    auto last = m.length();

    while(first < last)
    {
        auto mid = first + (last - first) / 2;
        // the peak cannot be 'end'
        // if mid belongs to the left half 
        if(mid == begin || m.get(mid - 1) < m.get(mid) )
        {
            first = mid + 1;
        }
        else
        {
            last = mid;
        }
    }

    return first - 1;
}
template<typename Compare>
auto bsearch(size_t first, size_t last, int target, MountainArray& m, Compare cmp) -> size_t
{
    while(first < last)
    {
        auto mid = first + (last - first) / 2;
        if(cmp(m.get(mid), target))
        {
            first = mid + 1;
        }
        else
        {
            last = mid;
        }
    }

    return first;
}

class Solution {
public:
    int findInMountainArray(int target, MountainArray &m) {
        auto peak_index = peak(m);
        // try to search on the first half
        if(auto idx = bsearch(0, peak_index, target, m, less<int>{});
            idx != peak_index && m.get(idx) == target)
        {
            return idx;
        }
        // search on the second half
        if(auto idx = bsearch(peak_index, m.length(), target, m, greater<int>{});
            idx != m.length() && m.get(idx) == target)
        {
            return idx;
        }

        return -1;
    }
};

矩阵查找

LC74 Search a 2D Matrix

在一个$m \times n$的二维数组中，每一行从左到右递增，每一列从上到下递增。在这样的二维数组中做查找。

解法1:复杂度为$O(m + n)$

从数组的右上角row = 0; col = matrix.front().size() - 1开始看：

如果这个元素比target小，那么这个元素所在这一行的所有元素都比target小。因此我们可以把这个元素所在这行全部划掉。
如果这个元素比target大，那个这个元素所在这一列的所有元素都比target大。因此我们可以把这个元素所在这一列全部划掉。
如果这个元素和target相等，返回true

如果搜索空间为空，返回false

code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix.front().empty()) return false;
        int m = 0;
        int n = matrix.front().size() - 1;

        while(m <= matrix.size() - 1 && n >= 0)
        {
            if(matrix[m][n] > target) --n;
            else if(matrix[m][n] < target) ++m;
            else return true; 
        }
        return false;
    }
};

解法2：展开成一维数组二分查找

复杂度$O(\mathrm{log}(mn))$
思路一：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
这个二维数组，每一行拿出来拼在一起也是一个有序数组。所以我们可以把这个二维数组的坐标(i, j)唯一映射到一个坐标k上，然后在这个区间上做二分查找。

设m为该数组的行数，n为该数组的列数

k 对应的横坐标为 k / n
k 对应的纵坐标为 k % n

k 的范围为 [0, m * n)

code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix.front().empty()) return false;
        auto m = matrix.size();
        auto n = matrix.front().size();

        size_t first = 0;
        size_t last  = m * n;
        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            // mid < target
            if(matrix[mid / n][mid % n] < target) first = mid + 1;
            else last = mid;
        }
        
        return first != m * n &&
               matrix[first / n][first % n] == target;
    }
};

解法3：两次二分查找

复杂度$O(\mathrm{log}(m) + \mathrm{log}(n))$

在最后一列上做一次lower_bound，确定这个数应该在哪一行。检查一下该行是否有效。再在这行上做lower_bound确定他在哪一列。检查这一列是否有效，并检查结果是否的确相等。

注意：
每次用lower_bound做二分查找后，都要检查：

结果是不是end？
结果跟target等不等？

code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix.front().empty()) return false;
        auto m = matrix.size();
        auto n = matrix.front().size();
        // we first search the last col
        auto first = 0;
        auto last  = m;
        // elements in the last col : k --> (k, n - 1)
        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if(matrix[mid][n - 1] < target) first = mid + 1;
            else last = mid;
        }
        
        auto row = first;

        // check if the row we found is valid
        if (!(row < m)) return false;

        // we then search this row
        // k --> (row, k)
        first = 0;
        last  = n;
        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if(matrix[row][mid] < target) first = mid + 1;
            else last = mid;
        }

        auto col = first;
        // we found the solution, check it is not end
        return col < n && matrix[row][col] == target;

    }
};

LC240 Search a 2D Matrix II

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

这个题和上一个题不一样了，所以解法2，3就用不了了。但是解法1还是照常使用。

思路1：同上一题解1。复杂度$O(M + N)$

思路2：对角线二分查找。复杂度$O(\mathrm{log}(M!N!))$ = $O(MN\mathrm{log}(MN))$。大部分情况不如上面的线性搜索好。

矩阵对角线上的元素是递增的：因为一个元素$a{i,j}$小于他右边的元素$a{i,j + 1}$，也小于他下边的元素$a{i - 1,j}$。其对角线上的元素$a{i + 1, j + 1}$大于$a{i,j + 1}$也大于$a{i - 1,j}$。所以对角线上的元素是递增。并且对角线上的元素$a{i,j}$是它和矩阵右下角的元素$a{m - 1, n - 1}$构成的子矩阵的最小值。
我们可以现在该矩阵的对角线元素上做upper_bound，将不合适的子矩阵排除。然后在剩余的对角线元素确定的行和列上分别做lower_bound寻找该元素。

复杂度高，代码复杂导致运行时间隐藏的常数项也大。实现略。

数学上的二分查找

第N个神奇数字

小于等于x，能被A整除的数字有⌊x/A⌋个
小于等于x，能被B整除的数字有⌊x/B⌋个
小于等于x，能同时被A和B整除的数字有⌊x/lcm(A,B)⌋个
其中lcm(A,B)=ABgcd(A,B)为A和B的最小共倍数。
小于等于x，能被A或B整除的数字有⌊x/A⌋+⌊x/B⌋−⌊x/lcm(A,B)⌋个，记该数字为f(x)
维护循环不变式：

[begin, first)区间中的数字，f(x)<N
[last, end)区间中的数字,f(x)>=N
first < last

code

template<typename N>
inline decltype(auto) num(N x, N A, N B)
{
    return x / A + x / B - x / lcm(A, B);
}

class Solution {
public:
    int nthMagicalNumber(uint64_t N, uint64_t A, uint64_t B) {
        auto first = int64_t{};
        auto last  = UINT64_MAX;

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if(num(mid, A, B) < N)
            {
                first = mid + 1;
            }
            else
            {
                last = mid;
            }
        }

        return first % uint64_t(1e9 + 7);
    }
};

不用乘除取余做除法

LC29 Divide Two Integers

因为不允许使用int64_t，导致边界条件判断非常复杂。再加上LeetCode编译器不允许负数位移，可以说是LeetCode恶心之最。TODO

求整数的平方根

LC69 Sqrt(x)
这个题目承诺提供的数字x一定是一个非负整数。

会用接近INT_MAX的数来测试，可能会导致二分

思路1：二分查找

维护以下的循环不变式

first左侧区间数字的平方比x小
last右侧区间的平方x大
first - last > 1

解法：

初始化搜索区间为first = 0和last = n
找到区间中点mid
检测中点的平方mid * mid
- 如果 mid * mid < x移动first到mid (为什么不像以前一样是 mid + 1呢？因为mid * mid < x只能保证$[mid - 1, mid]$的数组的平方比x小)
- 如果 mid * mid > x移动last 到mid
- 如果 mid * mid == x 返回 mid
  注意：
非lower_bound形式的一般二分搜索，循环结束条件为last - first > 1

code

class Solution {
public:
    int mySqrt(int x) {
        if(x == 1 || x == 0) return x; //1和0是不能进入下面的循环的，直接返回就行了
        int first = 0;
        int last  = x;
        int64_t mid = x;
        while(last - first != 1){
            mid = first + (last - first) / 2;
            if(mid * mid < x)      first = mid;
            else if(mid * mid > x) last = mid;
            else                   return mid;
        }
        return first;
    }
};

思路2：lower_bound

套用lower_bound的一般套路，找到首个平方不小于x的数first，然后判断first的平方是否等于x，否则返回first - 1。

注意：

如果first用int，无法通过INT_MAX的测试，因为无法计算first * first的值，需要全部使用int64_t才行。

code

class Solution {
public:
    int mySqrt(int x) {
        int64_t first = 0;
        int64_t last  = x;
        int64_t mid = 0;
        while(first < last)
        {
            mid = first + (last - first) / 2;
            if(mid * mid < x)  first = mid + 1;
            else last = mid;
        }

        return first * first == x ? first : first - 1;
    }
};

思路3：upper_bound

找到首个平方大于x的数first，然后回first - 1即可。

code

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0 || x == 1) return x;
        int first = 0;
        int last  = x;
        int64_t mid = 0;
        while(last - first > 0)
        {
            mid = first + (last - first) / 2;
            if(x < mid * mid)  last = mid;
            else first = mid  +1;
        }

        return first - 1;
    }
};

困难二分查找

分割数组的最大值

LC410 分割数组的最大值

思路：

数组nums的子数组各自和的最大值，在$[max(nums), sum(nums)]$之间。
分成的数组越多，和的最大值就越小。分成的数组越少，和的最大值就越大。（未证明）
所以我们可以在前面的范围上做二分查找（未证明）
- 设以mid为子数组和的最大值，能将原本的数组分成k份
  - 如果 k < m，那么分的组数少了，说明mid选大了
  - 否则就是mid选小了
    注意：
和要用int64_t，因为有的测试用例会恶心你。
这个题的关键部分都缺少证明，估计也很难证明这个算法的正确性。所以把他记下来就好了。

code

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        // we first compute the max element in nums
        // and the sum of all elements in nums
        
        // the sum of all ints may make int overflow
        // thus we use int64_t

        int64_t sum = 0;
        int64_t max = INT64_MIN;

        for(auto x : nums)
        {
            max  = max < x ? x : max;
            sum += x;
        }

        auto first = max;
        auto last  = sum;

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            // using this mid we could count how many 
            // groups we could divide nums into

            int cnt = 1;
            int64_t tmp = 0;

            for(auto x : nums)
            {
                tmp += x;
                // if the sum exceeds the mid
                // they could form a group
                if (tmp > mid)
                {
                    tmp = x;
                    ++cnt;
                }
            }
            // if the group numbers > m, mid is too small
            if (cnt > m) first = mid + 1;
            else         last  = mid; 
        }
        return first;
    }

    
};

排序数组的中位数

LC4 Median of Two Sorted Arrays

中位数的定义：

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

假设现在有两个有序集合A, B。其划分后的状态如下，左边集合的元素个数为i - 1 - 0 + 1 + j - 1 - 0 + 1 = i + j个，右边集合的元素个数为m - 1 - i + 1 + n - 1 - j + 1 = m - i + n - j个

1
2
3

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

我们定义：

如果m + n为奇数，集合不能被正好平分。定义中位数为max(A[i - 1], B[j - 1])，即左边集合中的最大值。
如果m + n为偶数，则中位数为(max(A[i - 1], B[j - 1]) + min(A[i], A[j])) / 2，即左边集合的最大值和右边集合最小值的平均值。这样刚好将集合平分。

我们想要寻找的是下标i的值。注意到根据元素个数相等，可以列出等式：

总个数为偶数：i + j = m - i + n - j
总个数为奇数：i + j - 1 = m - i + n - j

采用整数除法，并假设n >= m，则总有下面的式子成立，我们可以通过i的位置来唯一确定j的位置：

j + j = m + n - i - i + 1 <=> j = (m + n + 1 / 2) - i

运用二分查找的思想，[begin, first)的区间上点的都比较小，也就是说满足A[i - 1] < B[j]。我们令mid = i - 1，mid2为其在B数组上的对应点，mid2 = (m + n + 1)/2 - mid1，则其对应的j - 1应该是mid2 - 1。因此区间[begin, first)上的点都满足A[mid1] < B[mid2 - 1]。我们找到二分查找的最关键的区间划分不等式。所以整个二分查找过程应该为：

first = 0
last  = m
while: first < last 
{
    mid1 = first + (last - first) / 2;
    mid2 = (m + n + 1 / 2) - mid1;
    if(mid1 != m && 
       A[mid1] < B[mid2 - 1]) 
          first = mid + 1;
    else  last = mid;
}

我们可以假设两个数组左边都是INT_MIN，右边都是INT_MAX。在计算出i的值后，我们还需找到中位数。我们需要计算：

左边区间的最大值max(A[i - 1], B[j - 1])
右边区间的最小值min(A[i], B[j])
但是存在i == m, i == 0, j == 0, j == n的特殊情况。根据上面提出的假设解决这些特殊情况即可。

剩下还需要处理的特殊情况就是较小的数组为空数组，此时会导致下标溢出。直接求长数组的中位数即可。

code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);

        // the shorter one is empty
        if(nums1.size() == 0)
        {
            if(nums2.size() & 1)
            {
                return nums2[nums2.size() / 2];
            }else
            {
                return (nums2[nums2.size() / 2] + nums2[(nums2.size() - 1) / 2])/ 2.;
            }
        }

        int half = (nums1.size() + nums2.size() + 1) / 2;
        int first = 0;
        int last  = nums1.size();

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            auto j = half - mid;
            // we have to make sure mid is not nums.size() to avoid overflow.
            // prove: TODO
            if(mid < nums1.size() && nums1[mid] < nums2[j - 1])
                first = mid + 1;
            else  last = mid;
        }

        auto maxLeft  = 0;
        auto minRight = 0;
        auto i = first;
        auto j = half - i;

        // compute maxLeft
        if(j == 0) maxLeft = nums1[i - 1];
        else if(i == 0) maxLeft = nums2[j - 1];
        else maxLeft = max(nums1[i - 1], nums2[j - 1]);

        // compute minRight
        if(j == nums2.size()) minRight = nums1[i];
        else if(i == nums1.size()) minRight = nums2[j];
        else minRight = min(nums1[i], nums2[j]);

        if( (nums1.size() + nums2.size()) & 1)
        {
            return maxLeft;
        }
        else
        {
            return .5 * (maxLeft + minRight);
        }
    }
};

2019年8月的思路

基本思路：

首先我们要找出两个数组当中较短那个，在短数组上做二分查找。设短数组为nums1，长数组为nums2
采用左闭右开的区间划分方式，初始化搜索空间为first = 0和last = nums2.size()。
找到短数组中点mid1
找到长数组对应的中点mid2 = (len1 + len2 + 1)/2 - mid1
我们维护循环不变式mid1之前的所有数都小于中位数，mid2之前的所有的数都小于中位数
- 如果 mid = 0，则nums[mid - 1] = INT_MIN
- 如果 mid = nums.size()，则nums[mid] = INT_MAX
- 如果 nums1[mid1 - 1] <= nums2[mid2] && nums2[mid2 - 1] <= nums1[mid1] 我们就找到了想要的位置。
- 如果 nums1[mid1 - 1] > nums2[mid2] 说明我们找大了，应该first = mid1 + 1
- 如果 nums2[mid2 - 1] > nums1[mid1] 说明我们找小了，应该last = mid
  -从维护循环不变式的角度分析：
  TODO
为什么mid2 = (len1 + len2 + 1)/2 - mid1？
TODO
INT_MIN和INT_MAX怎么回事？（怎么处理一个和最后一个元素的【左】和【右】？)
证明这种做法的正确性：
TODO

返回值为什么是max()/min()的形式？
TODO

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() < nums2.size())
            return findMedianSortedArraysImp(nums1, nums2);
        else
            return findMedianSortedArraysImp(nums2, nums1);
    }
    double findMedianSortedArraysImp(vector<int>& nums1, vector<int>& nums2){
        size_t len1 = nums1.size();
        size_t len2 = nums2.size();
        size_t first = 0;
        size_t last  = nums1.size();  
        while(!(last < first)){
            auto mid1 = first + (last - first) / 2 ;
            auto mid2 = len1  + (len2 - len1 + 1) / 2 - mid1;             
            auto mid1L = mid1 == 0    ? INT_MIN : nums1[mid1 - 1];
            auto mid1R = mid1 == len1 ? INT_MAX : nums1[mid1];
            auto mid2L = mid2 == 0    ? INT_MIN : nums2[mid2 - 1];
            auto mid2R = mid2 == len2 ? INT_MAX : nums2[mid2];
            if(mid1L <= mid2R && mid2L <= mid1R){
                if( (len1 & 1) == (len2 & 1) ) 
                    return (max(mid1L, mid2L) + min(mid1R, mid2R)) / 2.0;
                else 
                    return max(mid1L, mid2L);
            } 
            else if ( mid1R < mid2L ) first = mid1 + 1;
            else                      last  = mid1;
        }        
        return 0.;
    }
};

参考：
LC官方题解

动用二分查找模版来巧妙解决此题

LeetCode 004 详细分析

Binary Search : Median of two sorted arrays of different sizes.

完全二叉树的节点个数

LC222 完全二叉树的节点个数

完全二叉树除了最后一层，其他层都是填满的。设完全二叉树的层号为$0, 1, 2, \cdots n$，则第$n$层的节点数为$2^n$个，之前所有层的节点总数为$2^n - 1$个。所以关键是要找到最后一层有多少个节点。设最后一层的节点序号为$0, 1, \cdots, 2^n - 1$。如果想要检查一个序号为idx的节点是否存在，我们可以通过二分查找的方式找到从根节点到他的路径。即找到区间中点mid，mid < idx就first = mid + 1然后往右走，否则last = mid然后往左走。最后区间为空的时候，看看是不是节点是否存在。我们在最后一层的所有序号上再进行一次二分查找，确定最后一个存在的序号即可。

注意：

不知道为什么，在检查最后一层节点是否存在的函数中，last要设置为最后一层的节点数-1，如果按照左闭右开设置为最后一层的节点数，结果不正确。

code

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int lastLevel = depthOfCompleteBinaryTree(root) - 1;
        // compute num of nodes in last level
        int lastNodeNums = 1;
        while(lastLevel)
        {
            lastNodeNums *= 2;
            --lastLevel;
        }

        int first = 0;
        int last  = lastNodeNums;

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if(nodeExistsInLastLevel(root, lastNodeNums, mid))
                first = mid + 1;
            else
                last  = mid;            
        }
        
        return lastNodeNums - 1 + first;
    }

    int depthOfCompleteBinaryTree(TreeNode* root)
    {
        auto depth = 0;
        while(root)
        {
            root = root->left;
            ++depth;
        }

        return depth;
    }

    bool nodeExistsInLastLevel(TreeNode* root, int last, int idx)
    {
        int first = 0;
        // cannot use [) convention in Cpp, does not know the reason for this
        // we must decrease the len by one, otherwise it does not work
        --last;

        while(first < last)
        {
            auto mid = first + (last - first) / 2;
            if(mid < idx) 
            {
                first = mid + 1;
                root = root->right;
            }
            else
            {
                last = mid;
                root = root->left;
            }
        }

        return !(root == nullptr);
    }
};

基础知识

求区间中点

比较符号

STL中相等(equality)和等价(equivalence)的区别

实现lower_bound 和 upper_bound

[first, last) 左闭右开区间表示法

实现binary_seach

通过lower_bound实现binary_seach

实现equal_range

简单二分查找

单侧二分查找

有序数组上的次数统计

有序数组上缺失的数字

数组中数值和下标相等的元素

旋转数组

峰值数组

矩阵查找

数学上的二分查找

第N个神奇数字

不用乘除取余做除法

求整数的平方根

困难二分查找

分割数组的最大值

排序数组的中位数

完全二叉树的节点个数

实现`lower_bound` 和 `upper_bound`

实现`binary_seach`

通过`lower_bound`实现`binary_seach`

实现`equal_range`