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!




Get Free Tutorials by Email

About the Author

is the main author for cs-fundamentals.com. He is a software professional (post graduated from BITS-Pilani) and loves writing technical articles on programming and data structures.

Today's Tech News

Robotic barman pours Rory a pintPosted on Friday March 24, 2017

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

Row over US ISP customer data salesPosted on Friday March 24, 2017

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

Ofcom plans instant payback for broadband woesPosted on Friday March 24, 2017

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

Courtesy BBC News