Question

You are asked to write an efficient Pseudocode to search a given key within a given 2D array, where every row and column is sorted in an ascending order. For example consider a 2D array. Every row and column is sorted. You are searching the 2D array for key 36.  

3 7 11 23 45

5 9 13 25 50

7 14 15 30 55

10 18 22 34 62

16 24 29 38 88

Write and execute a java implementation of pseudocode your using the Codio platform. Test the correctness of your program using the test data given.

Answer 1

Pseudocode

• Set a 2D array, Array
• Set a key to search, key
• Set rowlength=length(Array)
• set columnlength=length(Array[0])
• For i=1 To columnlength

             if Array[rowlength][i]==key

              Display found message

                   Exit from program

             ElseIF Array[rowlength][i]>key

                   For j=1 To rowlength

                       If Array[j][i-1]==key

                           Display found message

                           Exit from program

                      End If

                   End

             End If

          End

• Display Not found message

Screenshot

public class TwoDSortedArraySearch 36 not Found in the array public static void main (String [] args) //Test array int testArray[]]=new int[][] {{3,7,11,23,45}, {5 //Test key int key 36; //Loop through last row for(int i-0;i<testArray [ 0] . length ; i++) { //Any colum match the key if (testArray[testArray.length-1][i]-key) System.out.println ( key+" Found in the row System.exit(0); //Find which column greater than key else if (testArray [ 0] [i]>key) { /Loop through all rows 1 less than i col //If found match display for(int j-0;j<testArray . length; j++ { if (testArray[j][i-1]==key) System.out.println ( key+" Found in System.exit(0); } //Not found case System.out.println ( key+" not Found in the array"); } }
Program

public class TwoDSortedArraySearch {

   public static void main(String[] args) {
       //Test array
       int testArray[][]=new int[][] {{3,7,11,23,45},{5,9,13,25,50},{7,14,15,30,55},{10,18,22,34,62},{16,24,29,38,88}};
       //Test key
       int key=36;
       //Loop through last row
       for(int i=0;i<testArray[0].length;i++) {
           //Any colum match the key
           if(testArray[testArray.length-1][i]==key) {
               System.out.println(key+" Found in the row "+(testArray.length)+" column "+(i+1)+" in the array");
               System.exit(0);
           }
           //Find which column greater than key
           else if(testArray[0][i]>key) {
               //Loop through all rows 1 less than i column
               //If found match display
               for(int j=0;j<testArray.length;j++) {
                   if(testArray[j][i-1]==key) {
                       System.out.println(key+" Found in the row "+(j+1)+" column "+(i)+" in the array");
                       System.exit(0);
                   }
               }
           }
       }
       //Not found case
       System.out.println(key+" not Found in the array");
   }
}

-------------------------

Output

36 not Found in the array