1

This is going to be a rather large question from me since it requires deep and thorough understanding of the problem and also various approaches taken up to now for the optimal solution.

For this matter, I will create a blog later on this as it requires little bit of time from my side to write up the contents and so forth.So, I will provide my blog link once it's ready.

Nevertheless, I am posting this so that we can get started discussing.

First thing first:

The problem is as follows:

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional >array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1] Table[i][j] ≤ Table[i + 1][j].

Here to be noted that each rows and columns are monotonically sorted i.e. each rows and columns are sorted in non-decreasing (lexicographical) order.

For the actual problem and a nice discussion on this problem, click on the following link:

Note:This post has part 1,2 and 3.

Searching 2D Matrix

Hong Shen, from Griffith University, Australia in December 27, 1995 published the optimal solution for this problem to be O(mlog(2n/m)) for a serial algorithm.

Hong Shen-- Generalized Optimal Matrix Search

Since then a lots of forum discussions, blogs, and online and offline articles and publications have been made on this, but as of today, as far as I know, O(((log(n))2) is the best claimed on this article with Improved Binary Search.

Even though the detailed algorithm has not been provided.

Now, I have done different variations of solutions on this problem in the hope to bring the optimal solution to be lower than the current best(I think)

However, I am not that good at the analysis of time complexities of algorithms.

The following is just one of them. As we come up with decisions I will keep providing others and thus come up with the best with all your helps.

Here's the first one for you to analyze the time complexity

  /*  NIAZ MOHAMMAD

    IntPol2d.cpp

    1. Find the interpolated mid along column
    2. Compare key with each elements in row-wise 
       along the found mid column
    3. IF failed
        DO 
        RECURSIVE call to IntPol2d 
        a. IF(key > a[row][mid])
            THEN SET l = mid + 1 and d = row - 1;
        b. ELSE set r = mid -1 and u = row;
*/


    bool intPol2d(int mat[][6], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol,int &count) {
      count++;
      if (l > r || u > d) return false;

      if (target < mat[u][l] || target > mat[d][r]) return false;

      int mid = l + ((target - mat[u][l])*(r-l))/(mat[d][r]-mat[u][l]);
      int row = u;

      while (row <= d && mat[row][mid] <= target) 
      {
        if (mat[row][mid] == target) 
        {
          targetRow = row;
          targetCol = mid;
          return true;
        }
        row++;
      }
      return intPol2d(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol,count) ||
             intPol2d(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol,count);

    }

If you require the whole executable code, please let me know.

Thanks for your patience and help and see ya on the discussion board :

Note: @ Admins or moderators, let me know if this is not the right place for this type of lengthy question, then I will move to my blog.

Niaz Mohammad
  • 41
  • 1
  • 8
  • What does "O(((log(n))2)" mean, and why does it not involve m? What do you think the complexity of your code is? If you can't analyze complexity, what gives you such confidence that you can beat Hong Shen? Why do you pass M and N and never use them? – Beta Jun 19 '11 at 14:06
  • 1. This one is claimed on the link provided "Searching a 2D matrix" and in this case he assumed it to be a square matrix. – Niaz Mohammad Jun 19 '11 at 14:22
  • 1
    You're a beginner? Then you're attempting a problem well beyond your skill (and asking us to do the work). Start with something simpler, like some basic searching and sorting algorithms. Once you master those you'll be better equipped to tackle a problem like this. – Beta Jun 19 '11 at 16:54

1 Answers1

0

you do not have to treat the array as a 2 dimensional thing. It is just a mat[n], where n=MxN and do a binary search with complexity O(log(n)). note this is log base 2 and is the worse case. Note that complexisies do not include constants others than 1 because they don't change with input size. The actual worst case is 2*log(n) elements tested. Also, You may hit the one you want on the first test. You can't get faster than that without prebuilding a hashtable or other associative array where pointer to the element in the original matrix you are looking for is at the index in the new array. You want element with value 46, so you look in your index table at element index 46, which, say, points you to (M,N)=(2357,656). Boom, complexity O(1) after the reusable, memory expensive, index table has been built.

MartyTPS
  • 530
  • 2
  • 5
  • No, we can't just flatten the array, the elements aren't sorted that way. We know only that for each element, its eastern and southern neighbour are both larger than it. So a matrix like [ 1 4 6 ][ 2 7 8] [ 5 8 9 ] is totally possible, which would be [ 1 4 6 2 7 8 5 8 9 ]. It's an interesting and fun problem, really. – SáT Oct 17 '11 at 00:48
  • ah ... that I did not catch. How many lookups per matrix? In other words are algorithms with expensive one time preparation and cheap repeated lookups possible? – MartyTPS Oct 18 '11 at 03:03
  • so binary search to look for subset of rows that start less than or equal and then iterative in that subset to find subset whose last element is greater than or equal to and then binary search inside that subset of subet to find column in row (all of them if you need all matches or first match if you only need one). – MartyTPS Oct 18 '11 at 03:07
  • worse case would be something like: 2*log(n)*n*2*log(3) -> O(n*log(n)) – MartyTPS Oct 18 '11 at 03:11
  • There's better. [Here](http://stackoverflow.com/questions/6603070/find-an-element-in-a-sorted-matrix)'s another stackoverflow discussion of the problem, with the classical O(n) solution. If you want to discover it yourself, here's a hint: consider the special properties of the northeastern and southwestern elements. – SáT Oct 18 '11 at 03:50
  • Yes, I know that the best worst case attained as of now is O(n), however, I'm trying to see if it is possible to do better than that...Since I'm NOT that great in analyzing it, I need help from someone to help me understand the tc of my code segment provided. Thanks – Niaz Mohammad Jul 07 '12 at 16:22