相关疑难解决方法(0)

问题:给定一个矩阵,其中每行和每列都被排序,编写一个方法来查找其中的元素.

这是一个经典的面试问题,这是我的解决方案

boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
    if (hs > he || ws > we) 
        return false; 

    int m = (hs + he) / 2; 
    int n = (ws + we) / 2;

    if (matrix[m][n] == t)
    {
        return true;
    }
    else if (matrix[m][n] < t)
    {
        // find the ele in the same row, right to [m][n]
        F(m, m, n + 1, we);

        // find the ele in the same col, upper …

我总是遇到最困难的时候，而且我还没有看到对所谓如此普遍和高度使用的东西的明确解释。

我们已经知道标准的二分搜索。给定起始下限和上限，在 (lower + upper)/2 处找到中间点，然后将其与您的数组进行比较，然后相应地重新设置边界，等等。

但是，调整搜索以查找所需的差异是什么（对于按升序排列的列表）：

1. 最小值 >= 目标
2. 最小值 > 目标
3. 最大值 <= 目标
4. 最大值 < 目标

似乎这些情况中的每一个都需要对算法进行非常小的调整，但我永远无法让它们正常工作。我尝试更改不等式、返回条件、更改边界的更新方式，但似乎没有任何一致。

处理这四种情况的最终方法是什么？

我接受了采访,有以下问题:

在小于O(n)的时间内从排序的数组中查找唯一的数字.

Ex: 1 1 1 5 5 5 9 10 10
Output: 1 5 9 10

Run Code Online (Sandbox Code Playgroud)

我给出了解决方案,但那是O(n).

编辑: 排序的数组大小约为200亿,唯一数字约为1000.