Programming Tutorials and Interview Questions

Here we apply binary search on a 2D array in which every row is increasingly sorted from left to right, and the last number in each row is not greater than the first number of the next row.

However, the the primitive solution for this problem is to scan all elements stored in the input matrix to search for the given key. This linear search approach costs O(MN) time if the size of the matrix is MxN.

But, as we can see each row in the matrix is sorted and the first element of a row is greater than or equal to the last number of the preceding row; therefore, the matrix can be viewed as a sorted one dimensional array. If all rows in the input matrix are concatenated in top down order, it forms a sorted one dimensional array. And, in that case binary search algorithm is suitable for this 2D array.

#include <stdio.h> #define ROWS 3 #define COLS 4 int binSearchOnMatrix(int matrix[][COLS], int value); int main() { int twodarr[ROWS][COLS]; //two dimensional array int key; //search key int i, j; //counter variable int searchStatus; //1 if key is found, 0 otherwise. //read array printf("Enter %d x %d matrix in ascending order: ", ROWS, COLS); for (i = 0; i < ROWS; i++) for (j = 0; j < COLS; j++) scanf("%d", &twodarr[i][j]); printf("\nEnter search key: "); scanf("%d", &key); searchStatus = binSearchOnMatrix(twodarr, key); printf("Key (%d) is found: %d\n", key, searchStatus); } int binSearchOnMatrix(int matrix[][COLS], int key) { int start = 0; int mid, row, col, value; int end = ROWS * COLS - 1; while (start <= end) { mid = start + (end - start) / 2; row = mid / COLS; col = mid % COLS; value = matrix[row][col]; if (value == key) return 1; if (value > key) end = mid - 1; else start = mid + 1; } return 0; } OUTPUT ====== Enter 3 x 4 matrix in ascending order: 1 2 3 4 5 6 7 8 9 10 11 12 Enter search key: 5 Key (5) is found: 1

The above piece of code develops a function `binSearchOnMatrix`

that takes a two dimensional array and search key as input and returns either 1 or 0 depending upon the success or failure of search key found. The function `binSearchOnMatrix`

applies binary search on two dimensional matrix. It calculates `row`

and `col`

by dividing `mid`

by `COLS`

and `mid`

modulo `COLS`

respectively.

Hope you have enjoyed reading C program for binary search on two dimensional arrays. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

Facebook apologises after repeatedly restoring posts featuring stolen photos of children and posted claims they had cancer.

Malware researcher Anton talks about who does what in the web's dark marketplaces.

A pest control company develops a mouse trap that connects to the internet.