Skip to content

Instantly share code, notes, and snippets.

@anil477
Created December 27, 2017 11:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anil477/2f5d29bb04c1e0825b4c7e5e1614b5c2 to your computer and use it in GitHub Desktop.
Save anil477/2f5d29bb04c1e0825b4c7e5e1614b5c2 to your computer and use it in GitHub Desktop.
Search element in a sorted matrix
#include <bits/stdc++.h>
using namespace std;
const int r=5,c=5;
//assume matrix as a 1D array
// O(log(mn))
bool findElement(int arr[r][c],int l,int h,int x)
{
while(l<=h)
{
//get the middle index
int mid=(l+h)/2;
//get the corresponding row and column for middle element
// since index_1D_array=TotalColumns*(current row)+(current column)
int i=mid/c;
int j=mid%c;
cout<< " L: " << l << " H: " << h << " mid: "<< mid<<" "<< " i:"<< i << " j:" << j << " " << arr[i][j]<< " " << endl;
if(x==arr[i][j])
{
cout<<"Found at a["<<i<<"]["<<j<<"]";
return true;
}
if(x<arr[i][j])
h=mid-1;
else
l = mid+1;
}
return false;
}
int main() {
int arr[r][c]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
int l=0,h=r*c-1;
int x=24;
if(!findElement(arr,l,h,x))
cout<<"Not Found";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment