CC-16 : Search number in sorted matrix.

Description:

Given an input number and sorted matrix of numbers, find the number in the array.

Test cases and expected outputs:

Input Parameters	Expected outputs
The sorted matrix : 7,8,10,11, 19,29,33,40, 52,61,74,81,	Element: 33 found ? true Element: 64 found ? false

Pseudocode:

searchInSortedMatrix(nums[][], toSearch):

Integer matrix named nums and integer named toSearch to be searched are received as input parameters.

Set integer variable rows to nums.length.

Set integer variable cols to nums[0].length.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to rows*cols-1, we will use this variable to check the last index of partition in which are searching for required integer.

Initialize integer variables named row and col.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midIdx to (lastIdx-firstIdx)/2. We will use midIdx to partition the array into 2 partitions.

Set row to midIdx/cols.

Set col to mid%cols.

If (nums[row][col] >= toSearch) :

Set lastIdx to midIdx.

Else:

Set firstIdx to midIdx+1.

Set row to firstIdx/cols.

Set col to firstIdx%cols.

If (nums[row][col] == toSearch) :

Return true as we have found the required number in the input matrix.

Else :

Return false, as required number does not exist in the input matrix.

Code:

public boolean searchInSortedMatrix(int[][] nums, int toSearch){
	int rows=nums.length;
	int cols=nums[0].length;
	int firstIdx=0;
	int lastIdx=rows*cols-1;
	int row, col;
	while (firstIdx < lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		row=midIdx / cols;
		col=midIdx % cols;
		if (nums[row][col]>=toSearch) {
			lastIdx=midIdx;
		} else {
			firstIdx=midIdx+1;
		}				
	}	
	row=firstIdx / cols;
	col=firstIdx % cols;
	int findIdx;
	if (nums[row][col]==toSearch) {
		return true;
	}else {
	return false;
	}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchInSortedMatrix {

public boolean searchInSortedMatrix(int[][] nums, int toSearch){
	int rows=nums.length;
	int cols=nums[0].length;
	int firstIdx=0;
	int lastIdx=rows*cols-1;
	int row, col;
	while (firstIdx < lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		row=midIdx / cols;
		col=midIdx % cols;
		if (nums[row][col]>=toSearch) {
			lastIdx=midIdx;
		} else {
			firstIdx=midIdx+1;
		}				
	}	
	row=firstIdx / cols;
	col=firstIdx % cols;
	int findIdx;
	if (nums[row][col]==toSearch) {
		return true;
	}else {
	return false;
	}
}



public static void main(String[] args) {
	
	boolean retVal;
	try {
	SearchInSortedMatrix search=new SearchInSortedMatrix();
	int[][] nums = {{7,8,10,11},
					{19,29,33,40},	
					{52,61,74,81}
	};
	search.print2dArray(nums, "The sorted matrix");
	int toSearch=33;
	retVal=search.searchInSortedMatrix(nums, 33);
	System.out.print("\n\n Element: "+ toSearch+ " found ? " +retVal );
	
	toSearch=64;
	retVal=search.searchInSortedMatrix(nums, 64);
	System.out.print("\n\n Element: "+ toSearch+ " found ? " +retVal );
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
}
		
}



public void print2dArray(int[][] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("**************************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("**************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

}