如图,使用二分查找出现如下报错,请问这是怎么产生的,应该怎么解决
7条回答 默认 最新
关注 题主,你要二分查找法解题,若有帮助,还望采纳,点击回答右侧采纳即可。
思路:这种二维问题,首先想到动态规划, 如果统计找到某个值的步数,直接dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 可以先找到所在行,然后在二分查找。
解题方法:先遍历每行,再用二分查找
时间复杂度: O(mlogn)
空间复杂度: O(l)解题代码如下,请参考一下。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); int i = 0; //遍历每一行 while(i < m){ //查找target所在区间 if(matrix[i][0] <= target && matrix[i][n - 1] >= target){ //二分查找 int left = 0, right = n - 1; while(left <= right){ int mmm = left + (right - left) / 2; if(target > matrix[i][mmm]){ left = mmm+1; }else if(target < matrix[i][mmm]){ right = mmm-1; }else{ return true; } } } i++; } return false; } };
提交截图:
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥15 状态图的并发态问题咨询
- ¥15 PFC3D,plot
- ¥15 VAE模型编程报错无法解决
- ¥100 基于SVM的信息粒化时序回归预测,有偿求解!
- ¥15 物体组批优化问题-数学建模求解答
- ¥15 微信原生小程序tabBar编译报错
- ¥350 麦克风声源定位坐标不准
- ¥15 apifox与swagger使用
- ¥15 egg异步请求返回404的问题
- ¥20 Ti毫米波雷达板同步