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

HT·生活

123

 
 
 

日志

 
 

ex74 Search a 2D Matrix  

2015-05-18 22:02:54|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
二分查找的变形

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

还是有一点,注意up down的下标和边界条件,以及二分查找汇中left和right的边界条件,都是坑啊!!!
见c代码

bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {
int m, n;
m = matrixRowSize;
n = matrixColSize;

int up = 0, down = m - 1;
int mid;
while (up < down)
{
if (up == down || (up == (down - 1)))
break; //退出条件有两个,一个是up == down,还有一个是up == down-1
mid = (up + down) / 2;
if (matrix[mid][0] >target)
{
down = mid - 1; //不可能再mid这一行
}
else
{
if (matrix[mid][0] < target)
{
up = mid; //可能在mid这一行
}
else
{
return true;
}
}
}
int line;//确定到底在哪一行
if (up == down)
{
line = up; //就在这一行,接着用二分查找
}
else
{
if (matrix[down][0] > target)
{
line = up;
}
else
{
line = down;
}
}


int left = 0, right = n - 1;
while (left <= right)
{
mid = (left + right) / 2; // left + (right-left)/2
if (matrix[line][mid] > target)
{
right = mid-1; //去掉mid
}
else if (matrix[line][mid] < target)
{
left = mid+1; //刨去mid
}
else
{
return true;
}
}

return false;
}


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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