0

Design an algorithm , FindElement(a,p), where "a" is two-dimensional square array of positive integers with duplicates and each row of integers is in non - decreasing order: a[i][0] ≤ a[i][1] ≤ a[i][2] · · · ≤ a[i][n-1] (i=0,1,. . .,n-1),. The algorithm should define whether or not p is contained in a. It should return true if the "p" was founded, false otherwise. Your algorithm must be as efficient as possible. Algorithm should be based on Binary Search

I have found the following solution (but i'm not sure that it is correct):

Solution is to search for the element working on one row at a time using binary search. Binary searching a given sorted row of size (n) takes O(Log(n)) so it would take O(nlog(n)) to search the entire array in worst case.

Does this solution is suitable for the given task or not? I do not know how to implement this algorithm, please could you give me pseudo - code or explanation how to do it. Thanks in advance.

Improve this question
4
  • It's not clear 1. Whether you search for element equal to p or what? 2. If you have duplicates, what is the output? Indexes of all occurrences? 3. Do you really need to use binary search for this task (there is a more efficient ways to implement this request if you are allowed to allocate hash table). Please clarify the problem statement. Commented Nov 22, 2011 at 23:04
  • Actually, the 'square/2-dimensional array' is a red-herring - you conceptually (potentially) have something else, allowing the entire search to be performed in O(log n). None of the current answers reference this possibility (@Amit's is close, though). This does not necessitate allocating a hash table, or indeed any other variables other than the ones used for an O(n log n) search - you just have to think differently. I'm not revealing the actual answer, because I want you to think of it. Oh, and you don't mention if you need all occurrences, or only one (results quite different). Commented Nov 22, 2011 at 23:22
  • Search using perfect hash gives you O(1) in average (plus length of the output for this particular case). Commented Nov 22, 2011 at 23:25
  • Okay, I misread the specifications somewhat. The solution I've outlined is only valid if a[i][n-1] ≤ a[i+1][0] in all cases, which may not be the case here. Otherwise, your proposed solution should function just fine. Commented Nov 23, 2011 at 16:28

6 Answers 6

Reset to default
1

Yes, your solution seems correct and efficient (given your description of the initial problem, they probably want you to use binary search). Your algorithm should go something like this:

public Point FindElement(int[][] matrix, int number) {
    Point p = new Point(); // holds two integers and represents 
                           // a position in the matrix.
    int found = -1;
    for(int i = 0; i < N; i++) {
        found = binarySearch(matrix[i], number, 0, N);
        if(found != -1) { 
           p.setX(i); 
           p.setY(found); 
           return p; 
        }
    }
    return null;
}

where binary search can be implemented according to the pseudocode found here: http://en.wikipedia.org/wiki/Binary_search_algorithm#Recursive

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Assuming that outputting the first match you find is o.k., the above solution works, though you probably need to return both i and found so you get the row and column of the match. Also, if allowed, use Arrays.binarySearch() instead of writing your own.
Yes, you are right. Arrays.binarySearch() exists, although given that it's homework, they probably want a full implementation.
sorry I did not understand ow do you go through the all rows of the 2D array? You going through this loop : for(int i = 0; i < N; i++), where N is ? (i assume that it is the number of rows), then you call: found = binarySearch(matrix[i], number, 0, N);, so what is matrix[i]?
"matrix" is the input bidimensional array, like "a" in your description.
1

Yes solution is correct.

Here is the pseudo-code

     int index = -1;
    for (int i : height of array){
      int[] putIn1Darray = a[i][j] where j = 0 to n;
      index = Arrays.binarySearch(putIn1Darray,p); 
      if (index == -1)
          //Element not found yet
          continue;
      else
          //Element found
          break;   
    } 
    print index;

The above algorithm is used to display the first occurrence of element p.

You can modify it as per your HW.

Improve this answer

Comments

0

Binary Search only work on a sorted list. So if it is suitable: I would say yes. Just make sure that you step forward and backwards when you get an answer to get all the duplicates.

You can use this as a basis: http://www.java-tips.org/java-se-tips/java.lang/binary-search-implementation-in-java.html

Improve this answer

Comments

0

In real life, I would use java.util.Arrays.binarySearch if I can guarantee the data is sorted. I use the Arrays.sort function to sort an array or load up the data using TreeMap/TreeSet and use the get function.

Improve this answer

Comments

0

if I understand your problem description correctly, then you don't have any relations/constraints between the individual rows, right? Just elements within a single row are sorted in ascending order.

If you have to search a lot, just read the matrix as a list and sort it again. This takes time on the order of N^2*log(N). After that just do binary search on that collapsed list, which again will be on the order of log(N) as log(N^2) = 2*log(N).

The break-even point from where the preprocessing can be subsumed into the search time is when you search at least N times.

Improve this answer

Comments

0

Here is how I look at this problem:

There is a brute force way, semi brute force way, and an efficient way. I haven't see the efficient way listed here.

Assume it's a square matrix, with n = number of rows/columns

  1. Brute force way is linear search everything, O(n^2),

  2. Your method (along with other answers listed), O(n log n),

  3. More interesting answer, 2D binary search.

Let say you have a function that searches for a value in matrix, 

boolean findInMatrix(a, p)
{       
    if(a == null) 
        return false;
    //Compare the middle of the matrix with p

    if(p == a[n/2][n/2])
        return true;        

    if(a.length == 1)
        return false;       

    if p < a[n][n], then 
        return findInMatrix(top left, p) || findInMatrix(bottom left, p) || findInMatrix(top right, p);
    else 
        return findInMatrix(bottom right, p) || findInMatrix(bottom left, p) || findInMatrix(top right, p);
}

Boom, done. Of course, you need to handle how to pass in portion of the matrix to search, you can either use in place method by passing in 2D range, or you can copy matrix. As you can see, it's binary search x 3 on every iteration. Complexity should still be O(log N) where N is total number of cells, n^2.

What inspired me for this solution is that I think we should make full use of the given properties instead of just 1 dimension sort search which is only using half.

Please let me know if my solution is wrong.

Note: Oops, I misread the question as Clockwork-Muse. This solution doesn't apply to the question.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.