Write a C program to perform binary search on two dimensional (2D) array.

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!