Click here to Skip to main content
15,868,016 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
I want to write a function that looks for an integer value in a sorted, 2-dimensional array. The function should return a Boolean indicating whether the integer was found.
The function prototype in C#: public static bool Contains (int value, int[][] grid);
The sorted, 2-dimensional array always has N rows and N columns. For the grid the following assertions must hold true:
1) The values in each row increase as the index increases
2) The values in each column increase as the index increases


As an example of a valid grid that might be passed in to the function:
(0, 0)
      [ 0 ] [ 1 ] [ 20 ] [ 22 ]
      [ 2 ] [ 4 ] [ 21 ] [ 30 ]
      [ 3 ] [ 5 ] [ 23 ] [ 31 ]
      [ 24] [ 25] [ 26 ] [ 32 ]
                                 (3, 3)

In your response, please indicate the runtime and memory complexity of your solution using Big O notation.


Thank you!
Posted
Updated 13-Dec-10 21:28pm
v2
Comments
Manfred Rudolf Bihy 14-Dec-10 3:29am    
Edit: Added "Homework" tag. Code tags.
Thomas Krojer 14-Dec-10 3:55am    
Sorry, but homework should be done by the student himself!

If you read the definition carefully, you will find the solution.
Toli Cuturicu 15-Dec-10 15:46pm    
prototype? :-)

You should do your own homework. We may help, sure, but you should show us, at least, some effort. Hence, please, try developing yourself a solution and ask here specific questions whenever you're stuck.
Good luck.
:)
 
Share this answer
 
v2
Comments
abu sabha 14-Dec-10 4:03am    
I didn't put it as homework, and this is not homework i just get this question from my manager and i want to fiend out how can i do it.

Thanks
Mark_Wallace 14-Dec-10 4:22am    
OK, forget my nagging about homework, too.
You really must not expect to be given code here. This is obviously a homework project, and copying code that someone else has written for you would be cheating.

However, if the logic of doing such things has not been explained adequately to you (or if you were "too busy" to listen to that bit), you are pretty much screwed.

I'll give you the logic, because it's a slow day and I'm bored, but next time read your course book and have a go yourself, before asking for help.

There are several ways to do it, but one of the most cost-efficient (although certainly not the prettiest) methods for a data set that size would probably be a simple comparison or two, followed by a succession of secondary comparisons.

If you have to make it work for a dataset of any size, change it to use a binary search on the diagonal values ([1,1], [2,2] ... [n,n]), then further binary searches "up and across".

The logic:
Stop if the number is found

test [2,2]

if [2,2] is greater 
  test [1,1] 
    if [1,1] is greater
      test [0,0]
      test-up-and-across(1,1)  
    else test-up-and-across(2,2)    
else test [3,3]
  if [3,3] is greater
    test-up-and-across(3,3)

test-up-and-down(x.y) 
  set n to x
  while n is not zero
    subtract one from n
    test [n,y]
  set n to y
    while n is not zero
      subtract one from n
      test [x,n]


It should be easy enough for you to code it from that, and doing so will make you understand what is being done by the code.

The Big O will depend on how you code it (most particularly on how you terminate it after finding the number).
 
Share this answer
 
Comments
Mark_Wallace 14-Dec-10 4:21am    
What idiot came to my computer and checked "Ignore HTML in text" while I was writing that?!?
abu sabha 14-Dec-10 4:29am    
Thanks Mark
but you have to know i'm not a programmer, like what i said before just my manager he give me this question, i don't know how to make it, in same time i don't want to waste your time thanks for help.
johannesnestler 14-Dec-10 9:12am    
why would any manager ask a non-programmer such a questions? are you kidding us? This is the kind of questions you are normally facing during education...
So if it's true, tell your manager you don't know - it's not your job. If to know such things is considered a condition for your job - you are in the wrong place.
Hi all

I wrote this code and working fine, but i don't know how to make Big O,
my code below :) :
C#
class Jagged
{
    static void Main()
    {
        int[][] grid = new int[4][];
        grid[0] = new int[4] { 0, 1, 20, 22 };
        grid[1] = new int[4] { 2, 4, 21, 30 };
        grid[2] = new int[4] { 3, 5, 23, 31 };
        grid[3] = new int[4] { 24, 25, 26, 32 };

        int value = 32;
        if (Contains(value, grid))
        {
            Console.Out.WriteLine("Your Value [" + value + "] found ");
        }
        else
            Console.Out.WriteLine("Your Value [" + value + "] Not found ");
    }
    public static bool Contains(int value, int[][] grid)
    {
        Console.Write("Your search Value is [" +value + "]");
        Console.WriteLine();
        Console.WriteLine();
        for (int i = 0; i < grid.Length; i++)
        {
            int[] innerArray = grid[i];
            for (int a = 0; a < innerArray.Length; a++)
            {
                Console.Write("[" + innerArray[a] + "]  ");

            }
            Console.WriteLine();
            Console.WriteLine();
            for (int a = 0; a < innerArray.Length; a++)
            {
                if (value == innerArray[a])
                {

                    return true;
                }
            }
            Console.WriteLine();
        }
        return false;


    }
}
 
Share this answer
 
v2
Comments
Toli Cuturicu 15-Dec-10 15:48pm    
Like a small o, only bigger: O

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900