1．给定如下的n*n的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增
1 2 3
3 5 6
4 8 9
现在要求设计一个算法， 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）（百度实习生笔试xx）
#include<stdio.h>
#include<stdlib.h>
void paixue(int temp[],int a[][10],int n)/*对输入的矩阵进行排序，排完序后在将矩阵放回*/
{
int i,j,k=0,temp1,count=0,min;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
temp[k++]=a[i][j];
count++;
}
for(i=0;i<count-1;i++)/*选择排序*/
{
min=i;
for(j=i;j<count;j++)
{
if(temp[min]>temp[j])
min=j;
}
if(min!=i)
{
temp1=temp[min];
temp[min]=temp[i];
temp[i]=temp1;
}
}
k=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=temp[k++];
}
zheban_find(int a[][10],int i,int k,int n)/*对输入的某个值进行折半查找*/
{
int left,right,middle;
left=0;
right=n-1;
while(left<=right)
{
middle=(left+right)/2;
if(k==a[i][middle])
return middle;
else if(k>a[i][middle])
left=middle+1;
else if(k<a[i][middle])
right=middle-1;
}
return -1;
}
void main()
{
int i,j,k,n,a[10][10],flag=0;
int *temp;
temp=(int *)malloc(100);
if(NULL==temp)
{
printf("allocation failture\n");
exit(0);
}
printf("请输入矩阵的行和列\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入矩阵的第%d行\n",i+1);
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("输入的矩阵是\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",a[i][j]);
}
putchar('\n');
}
paixue(temp,a,n);
printf("输入的矩阵排序后是\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",a[i][j]);
}
putchar('\n');
}
printf("请输入要查找的值\n");
scanf("%d",&k);
for(i=0,j=n-1;i<n;i++)
{
if(k<a[i][j]||k==a[i][j])
{
k=zheban_find(a,i,k,n);
if(k>=0)
{
printf("找到了K在矩阵的%d行，%d列\n",i+1,k+1);
flag=1;
}
}
}
if(flag==0)
printf("没有找到要找的数\n");
free(temp);
}
