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!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.