我得到了以下的面试问题。
有一个n x n元素的数组。该数组部分排序,即第i行中最大的元素小于第i+1行中最小的元素。如何在O(n)的复杂度下找到给定的元素。
这是我的解决方案:
您应该前往第n/2行。从那里开始比较,例如您搜索100并且您看到的第一个数字是110,那么您知道它要么在这一行中,要么在上面的行中,现在您走n/4行,以此类推。
从评论中得知:
总体而言, 不是 O(n * log n) 吗?因为他必须在每个二进制搜索达到的行中进行解析, 因此线性搜索的数量与他将要扫描的行数相乘。- Martin Matysiak 5分钟前。
我不确定这是一个正确的解决方案。有没有更好的方法?