Stuck - 我自己实现的多维二分搜索

Question

我对自己的二维数组二进制搜索实现有点困惑。它似乎没有迭代到下一行并保留在同一列中（因此是一个永无止境的循环）。二进制搜索的工作方式是从两个端点（低端点和高端点）之间的中间开始。如果查询太低，则将高端点重新调整为中间点 - 1。如果查询太高，则将低端点设置为中端点 + 1。所有这一切都会发生，直到查询找到，或者没有匹配项，从而导致 O(log n) 的最坏情况。但是，我似乎无法让数组逐行搜索值。这是我到目前为止所做的：

public static int count(int[][]array, int query) {

        int countoccurences = 0;        
        int low = 0;                        
        int high = array[0].length - 1;
        for (int row = 0; row < array.length; row++) {
            for (int column = 0; column < array[row].length; column++) {
                while (low <= high) {

                    int mid = (low + high) / 2; //Set mid point to be (low + high) divided by 2
                    if (array[row][mid] == query ) { //Check if middle value in each column is equal to the search query
                            countoccurences++; //If it is, increment countoccurences by 1
                        } else if (array[row][mid] < query) {
                            low = mid + 1; //If it is less than query then re-adjust low to be mid index + 1
                        } else  {                           
                            high = mid - 1; //if query is too low, re-adjust high to be mid index - 1
                        } 
                } 
            }
        }   


        return countoccurences;


    }



    public static void main(String[] args) {
        int[][] array = { {7, 4, 3, 5, 10},{8, 5, 4, 6, 11},{10, 10, 8, 10, 13}, {11, 10, 15, 10, 14}};
        System.out.println("Total occurences of the number 10 is: " + count(array, 10));
    }


}

谢谢！

Answer 1

我想你需要这样的东西

    public static int count(int[][] array, int query)
    {
        // nothing to find in an empty array
        if(array.length == 0)
            return 0;

        int countoccurences = 0;
        for (int column = 0; column < array[0].length; column++)
        {
            int low = 0;
            int high = array.length - 1;
            while (low <= high)
            {
                int mid = (low + high) / 2; //Set mid point to be (low + high) divided by 2
                if (array[mid][column] == query)
                {
                    // Check if middle value in each column is equal to the search query
                    for (int row = low; row <= high; row++)
                    {
                        if (array[row][column] == query)
                            countoccurences++; //If it is, increment countoccurences by 1
                    }
                    break;
                }
                else if (array[mid][column] < query)
                {
                    low = mid + 1; //If it is less than query then re-adjust low to be mid index + 1
                }
                else
                {
                    high = mid - 1; //if query is too low, re-adjust high to be mid index - 1
                }
            }

        }
        return countoccurences;
    }

重要变化：

交换行和列以匹配数据的实际排序方向
针对列中有查询的情况引入了break;。这就是你的代码无限循环的原因
删除了外部 for (int column = 0; column < array[row].length; column++) 因为它没有意义
另一方面，添加了内部for (int row = low; row <= high; row++)。它应该涵盖同一行中有多个目标值的情况，例如数据中的第 3 列。这个内部循环也可以使用更有效的二进制搜索，但我太懒了。

Stuck - 我自己实现的多维二分搜索

Stuck - My own implementation of Multi-dimensional Binary Search

java

binary-search