0

所以我遇到了一个巨大的障碍......也许只是因为我的逻辑不存在，但我似乎无法自己解决这个问题。

我正在尝试修改BinarySearch，以便获得两个索引。

第一个索引是给定数字 x 的最左侧索引和最右侧。如果该数字不存在，则生成 [-1,-1]。

无论如何。我一直在尝试修改 BinarySearch，但似乎无法使其正常工作。任何指针将不胜感激。

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
    int mid = (low + high) / 2;
    int left = -1, right = -1;
    while(low <= high){
        mid = (low + high) / 2;
        if(A[mid] == x){
            int newMid = mid;
            //check left
            if(left == -1){
                left = mid;
                return BinarySearchDup(A, x, low, mid - 1);
            }
            else if(right == -1){
                right = mid;
                return BinarySearchDup(A, x, newMid + 1, high);
            }       
            return new Pair(left, right);
        }
        else if(A[mid] < x)
            return BinarySearchDup(A, x, mid + 1, high);
        else// (A[mid] > x)
            return BinarySearchDup(A, x, low, mid - 1);
    }
    //if there are no matches of the number then it returns -1
    return new Pair(-1, -1);
}
4

2 回答 2

0

我不确定我是否理解您的想法，但这就是它不起作用的原因：

您的代码相当于：

public static Pair BinarySearchDup(int[] A, int x, int low, int high){
    int mid = (low + high) / 2;
    if(low <= high){        
        if(A[mid] == x)
            return BinarySearchDup(A, x, low, mid - 1);
        else if(A[mid] < x)
            return BinarySearchDup(A, x, mid + 1, high);
        else// (A[mid] > x)
            return BinarySearchDup(A, x, low, mid - 1);
    }

    return new Pair(-1, -1);        
}

事实上，如果你进入 while 循环，你总是会返回，所以永远不会超过一次迭代。此外，如果 mid 的值为 x，那么由于 left 为 -1，您始终输入此 if 子句。或者，如果您不进入 while 循环，则只需返回 (-1, -1)。希望这可以帮助。

编辑：你不能只使用普通的二进制搜索然后简单地从找到的索引来回走，直到你得到整个范围？

于 2013-04-08T01:51:12.717 回答
0

要解决这个问题：

我正在尝试修改 BinarySearch 以便它获得两个索引。第一个索引是给定数字 x 的最左侧索引和最右侧。如果该数字不存在，则生成 [-1,-1]。

我会这样做：

1）进行二分搜索，除了不考虑目标匹配并立即结束，而是考虑它比你的目标大（例如你搜索它的左边）。当这个搜索结束时，它要么在目标的最左边，一个左边（取决于它的编码方式——在这种情况下只检查一个右边），或者它会被确认不存在。

2) 像 1) 一样进行二分搜索，但考虑目标小于目标。这将以类似的方式找到目标的最右侧实例。

这给了你 O(logN) 的复杂性。Petar Ivanov 的想法“你不能只使用普通的二分搜索，然后简单地从找到的索引来回走动，直到你得到整个范围吗？” 如果数组中有大量重复项，则可能与 O(N) 一样糟糕。但是，如果预期的重复计数（或预期的数组大小）很小，那么 Petar Ivanov 的想法在编码方面要简单得多，因为您不必使用更改的逻辑重新进行二进制搜索。

于 2013-04-08T03:25:23.163 回答