二维数组中的查找思路及正确代码

二维数组中的查找思路及正确代码

二维数组中的查找

• 二维数组中的查找
• • 代码思路：
  • bug1:
  • bug2
• 正确代码

二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。
剑指offer上给出的答案是从右上角或左下角的数开始排除查找，我正在尝试使用二分查找的方法，代码完成但是还存在些bug。
（正确代码在最后，bug都是废话 ）

代码思路：

bug1:

error:表达式必须包含指向对象的指针类型；
错误的代码是：(使用二分查找和排除查找都会出现这个错，目前还不知道出错的原因。）

bool Find(int i,int j,int* arr,int key)//二分查找
{int low=0;int high=j-1;while(low<high){int mid=(int)(low+high)/2;if(arr[low][mid]==key)//mid出错{printf("成功n");return true;}if(arr[low][mid]>key)//mid出错{high=mid-1;}if(arr[low][mid]<key)//mid出错{low=mid+1;}}
}
bool Find2(int i,int j,int *arr,int key)//排除查找
{if(arr!=nullptr&&i>0&j>0){int low=0;int high=j-1;while(i>low&&high>=0){if(arr[low*j+high]==key){printf("成功n");return true;break;}else if(arr[low*j+high]>key)//{--high;}else{++low;}}printf("失败n");return false;}
}
int main()
{int arr[4][4]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};Find(4,4,&arr[4][4],7);Find2(4,4,&arr[4][4],7);
}

bug2

无论key是否是二维数组中的数运行结果都是失败(我？？？）对不起还是没修改好，以下是错误代码（别问我为什么放错误代码我只是想让自己知道自己错在哪里）

#include<iostream>
#include<string.h>
using namespace std;bool Find(int i,int j,int* arr,int key)//二分查找
{int low=0;int high=j-1;while(low<high){int mid=(int)(low+high)/2;if(arr[low*i+mid]==key){printf("成功n");return true;}if(arr[low*i+mid]>key){high=mid-1;}if(arr[low*i+mid]<key){low=mid+1;}}
}
bool Find2(int i,int j,int *arr,int key)
{if(arr!=nullptr&&i>0&j>0){int low=0;int high=j-1;while(i>low&&high>=0){if(arr[low*j+high]==key){printf("成功n");return true;break;}else if(arr[low*j+high]>key)//{--high;}else{++low;}}printf("失败n");return false;}
}
int main()
{int arr[4][4]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};Find(4,4,&arr[4][4],7);Find2(4,4,&arr[4][4],7);
}

。。。我的代码怎么不是五颜六色的

正确代码

我成功了哈哈哈哈哈哈哈哈哈（其实写到这里还没有成功 等我明天问问老师在放正确的吧）
19-07-23
错在传的参数格式是一维数组（int *arr改为int arr[4][4]）main中（&arr改为arr）其实就是二维数组调用和格式的问题。。。。。

#include<iostream>
#include<string.h>
using namespace std;
bool Find2(int i,int j,int arr[4][4],int key)//这里的传参出现了问题，之前写的那种方式相当于传了一维数组，相当于只传了第一行
{if(arr!=NULL &&i>0&&j>0){int low=0;int high=j-1;while(i>low&&high>=0){if(arr[low][high]==key){printf("成功n");return true;break;}else if(arr[low][high]>key)//{--high;}else{++low;}}printf("失败n");return false;}
}
int main()
{int arr[4][4]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};Find2(4,4,arr,7);
}

二分查找的方法就先暂时放弃哈。。
代码并不完美，应该在函数中开辟一个二维数组再传行列数进行内存开辟和赋值。。