注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2014.12.27 Search in a 2-D Matrix 1  

2014-12-27 15:05:59|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Attention: 
The content in the article comes from book "Code interview".

Question:
In a 2-D matrix, 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. A sample matrix follows. Please implement a function to check whether a number is in such a matrix or not. It returns true if it tries to find the number 7 in the sample matrix, but it returns false if it tries to find the number 12.
1   3   5
7   9   11
13 15 17

Answer:
#include <stdlib.h>
#include <stdio.h>

void search_matrix( int matrix[], int width, int height, int target )
{
int start = 0;
int end = width * height - 1;
int i = ( start + end ) / 2;

if ( width * height == 1 ) {
if ( target == matrix[0] ) {
printf( "target %d exist in the matrix, index is (0, 0)\n", target );
} else {
printf( "target %d doesn't exist in the matrix\n", target );
}

return;
}

while ( i <= end && i >= start ) {
if ( matrix[i] == target ) {
printf( "target %d exist in the matrix, index is (%d, %d)\n", target, i/width, i%height );
return;
} else {
if ( matrix[i] < target ) {
start = i + 1;
} else {
end = i - 1;
}

i = ( start + end) / 2;
}
}

printf( "target %d doesn't exist in the matrix\n", target );
}

int main(int argc, char* argv[])
{
int data[] = {
1, 3, 5, 
7, 9, 11,
13, 15, 17,
};

search_matrix( data, 3, 3, 12 );

getchar();
}
  评论这张
 
阅读(256)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017