2的幂次NxN循环排序矩阵搜索的时间复杂度及优化方案咨询

问题1：现有实现的时间复杂度 #

你的实现时间复杂度是O(n²)，并没有更低：

• 你将NxN的矩阵拆为4个大小为(N/2)*(N/2)的象限，最坏情况需要遍历完目标所属的整个象限才能得到结果，总遍历次数为N²/4次，大O表示法会忽略常数系数，因此渐进复杂度依然是O(n²)。
• 额外提醒你现有代码有两处严重问题：一是如果目标值不存在于矩阵中，do-while循环没有设置行索引的上限，会进入死循环；二是象限pivot的定义错误，比如你标注的fourth_quarter_pivot取的是矩阵左下角元素，并不是第四象限的最大值，容易判错目标所属象限，开头的范围判断逻辑也存在逻辑漏洞，可能会把存在的目标误判为不存在直接返回false。

问题2：转一维有序数组再二分的方案是否更优 #

这个方案对于单次查询场景来说不是更优方案：

• 如果每次查询都要先遍历象限生成一维有序数组，生成过程本身就需要O(n²)的时间成本，加上二分的O(logn)开销，整体复杂度和你当前的实现没有差异，还额外占用了O(n²)的数组存储空间。
• 只有当你需要对同一个矩阵做多次查询时，可以提前预处理生成全局有序的一维数组，后续每次查询的复杂度可以降到O(logn)，这种场景下才划算。

更推荐的实现思路 #

如果你的矩阵满足「每行从左到右递增、每列从上到下递增」的特性，可以用经典的线性搜索方案，时间复杂度直接降到O(n)：

1. 从矩阵的右上角元素开始和目标比对
2. 当前元素等于目标直接返回true
3. 当前元素大于目标，向左移动一列（当前列所有元素都大于目标，直接排除）
4. 当前元素小于目标，向下移动一行（当前行所有元素都小于目标，直接排除）
5. 移动超出矩阵边界还没找到就返回false

内容的提问来源于stack exchange，提问作者anton5450