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

AlphaBay and Hansa dark web markets shut downPosted on Thursday July 20, 2017

The AlphaBay and Hansa marketplaces were known for trade in drugs, weapons and malware.

Kodi magazine 'directs readers to pirate content'Posted on Thursday July 20, 2017

The guide is being investigated by the Federation Against Copyright Theft.

Bitcoin swings as civil war loomsPosted on Thursday July 20, 2017

The Bitcoin community must agree how to tackle a slowdown in transaction times to avoid a schism.

Courtesy BBC News

AD BLOCKER DETECTED!

Advertisements help running this site for free.


To view the content please disable AdBlocker and refresh the page.

×