在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;
如果查找数字5,由于数组不含有该数字,则返回false。
我的解题思路是这样的矩阵行列都是从小到大排好序的,要查找的话自然用二分效率比较高,
而且这样的矩阵有个性质,最左上角的元素必定是最小值,最右下角的是最大值,在一个
n*n的矩阵中,对角线的元素也是排好序的,找到对角线上的一个元素,使得这个元素小于
待查找的key,并且下一元素大于待查找的key,那么只要在这个元素的左下角矩阵和右上角
矩阵递归继续对角线查找就可以了,例如上图例子里查找7,只要找到对角线的元素4,然后
递归查找红圈的矩阵就可以了
,左上角矩阵最大值4<7,右下角
矩阵最小值10>7,无需查找了,但是此题并没有告诉我们原始矩阵是n*n的,这是比较麻烦的
地方,不过思路是一样的,无非不能用对角线查找这样简单的办法了,假设m*n的矩阵,对角线
查找的办法改进为i = (m1+m2)/2,j = (n1+n2)/2 进行查找就可以了,(m1,n1)为矩阵最左上角
元素下标,(m2,n2)为最右下角元素下标
假设查找17,第一次比较10,然后比较25,然后比较13,返回元素13,这时候再递归查找13
左下角的矩阵和右上角的矩阵就可以了(红色椭圆部分);如果是查找9,第一次比较10,然后比较4,
然后比较6,返回元素6,这时候递归查找6左下角的矩阵和右上角矩阵(绿色椭圆部分)
代码如下:
a是二维数组首地址,(m1, n1)左上角坐标,(m2, n2)右下角坐标,参数n是矩阵一行的元素个数
int binsearch(int value, int *a, int n, int m1, int n1, int m2, int n2)
{
int begin_m1 = m1, begin_n1 = n1, end_m2 = m2, end_n2 = n2;
int left_result = 0, right_result = 0;
int i = (m1+m2)/2, j = (n1+n2)/2;
if (a == NULL)
return 0;
if (value < *(a+m1*n+n1) || value > *(a+m2*n+n2))
return 0;
else if (value == *(a+m1*n+n1) || value == *(a+m2*n+n2))
return 1;
while ((i!=m1 || j!=n1) && (i!=m2 || j!=n2)){
if ( value == *(a+i*n+j) )
return 1;
else if ( value < *(a+i*n+j) ){
m2 = i;
n2 = j;
i = (i+m1)/2;
j = (j+n1)/2;
}
else{
m1 = i;
n1 = j;
i = (i+m2)/2;
j = (j+n2)/2;
}
}
//search left & right
if ( i<end_m2 )
left_result = binsearch(value, a, n, i+1, begin_n1, end_m2, j);
if ( j<end_n2 )
right_result = binsearch(value, a, n, begin_m1, j+1, i, end_n2);
if (left_result | right_result )
return 1;
else
return 0;
}
- 大小: 59.6 KB
- 大小: 5.8 KB
- 大小: 12.6 KB
分享到:
相关推荐
在本资源中,我们将介绍Java数组的相关知识点,包括数组的逆序存放和输出、二分法插入数据到数组、计算二维数组对角线之和等。 一、数组的逆序存放和输出 在Java中,数组是一种基本数据结构,用于存储多个相同类型...
从给定的代码片段中,我们可以提取出三个主要的知识点:二分查找算法、杨辉三角的生成以及一维和二维数组的操作。下面将详细解释这些知识点。 ### 二分查找算法 二分查找(Binary Search)是一种在有序数组中查找...
题目的意思大致是在一个n*m的二维数组中,找到一个局部峰值。峰值要求大于相邻的四个元素(数组边界以外视为负无穷),比如最后我们找到峰值A[j][i],则有A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > ...
在二维数组中,如果一个元素比其上、下、左、右四个方向的元素都大,则该元素也是一个峰值。 #### 1. 一维峰值查找算法 **问题描述:** 给定一个一维数组,寻找其中的一个峰值。 **算法思想:** - 最简单的方法是...
在二维空间中,一个标准的圆方程是 (x-a)^2 + (y-b)^2 = r^2,其中(a, b)是圆心坐标,r是半径。如果有一系列点在平面上,我们可以利用这些点的信息,结合二分法,来逼近或重建这个圆的参数。 具体实现可能如下:...
同时也是二维数组,可以直接在c语言中使用,数组左列为unicode,根据unicode的数值大小从小到大进行排序,右列为对应的GB2312编码,旁边有注释对应的汉字,亲测可以在单片机上使用,建议用二分法搜索unicode然后转换...
在项目中,你需要设计一个棋盘视图,可以用二维数组来表示,每个元素代表棋盘上的一个格子。然后,实现二分法的逻辑,这通常包括以下几个步骤: 1. **初始化**:设定搜索范围,如从1到n(棋盘大小),并设置初始的...
例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,...
实例20 二维数组 实例21 字符数组 // 实例22 数组初始化 // 实例23 数组应用 实例24 函数的值调用 实例25 函数的引用调用 //swap 实例26 数组函数的调用 // 实例27 命令行变元 // 实例28 函数的返回值 实例29 函数的...
在计算机科学中,二分法通常用于查找和排序问题,但在这里,它被创造性地应用到了打乱数组元素的顺序上。二分打乱算法通常基于分治策略,将数组分为两半,然后随机交换两部分中的元素,以达到打乱顺序的效果。这种...
8. **二维数组的鞍点**:在矩阵中,鞍点是指行最大值和列最小值相等的元素。C语言中,处理二维数组通常涉及行遍历和列遍历,以及条件判断来找出鞍点。 9. **杨辉三角**:杨辉三角是组合数学中的一个重要概念,每行...
本篇将详细阐述数组函数、二维引用、多维引用以及二分法查找这四个核心知识点,旨在帮助用户提升在Excel中的计算和分析效率。 **一、数组函数** 数组函数是Excel中的高级功能,它能够处理一组或多组数据(即数组)...
二维数组最外边元素之和是指在二维数组中找到最外边元素的和。 4. 特定比特位置 0 和 15: 特定比特位置 0 和 15 是指在二进制数字中找到特定的比特位。 5. 字符串中的第一个和最后一个元素交换 字符串中的第...
实例20 二维数组 实例21 字符数组 实例22 数组初始化 实例23 数组应用 实例24 函数的值调用 实例25 函数的引用调用 实例26 数组函数的调用 实例27 命令行变元 实例28 函数的返回值 实例29 函数的嵌套调用 ...
二分法,也称为折半搜索法,是一种在已排序的数组或区间内查找特定元素的搜索算法。在数值分析中,它被用于求解连续函数的零点。基本思想是将区间不断减半,直到找到满足条件的解或区间变得足够小。这种方法简单且...
二维数组中的查找 数组 替换空格 字符串 从尾到头打印链表 链表,栈 重建二叉树 二叉树 用两个栈实现队列 栈,队列 斐波那契数列 动态规划 青蛙跳台阶问题 动态规划 旋转数组的最小数字 二分法 矩阵中的路径 dfs ...
12. 二维数组的地址计算:二维数组可以视为一维数组,a45的地址为1000 + 4 * (5 * 6 - 1),结果是1126,选A。 13. 树的度:节点的度是指其子节点的数量,B是A的父节点,有3个兄弟,所以B的度是4,选B。 14. 中序...
在C#中,通常使用二维数组或列表来存储中间结果。 6. **回溯法**:在解决搜索和组合优化问题时,如八皇后问题、N皇后问题、旅行商问题,回溯法是一种常用的策略。它尝试逐步构建解决方案,并在遇到无法继续的情况时...
8. 二维数组的存储:二维数组的体积(存储量)等于行数乘以列数乘以每个元素的字节数;末尾元素地址可以通过起始地址加上总字节数计算得出;按行或按列存储时,元素地址根据存储顺序计算。 9. 完全二叉树的性质:...
二维数组 Medium √ 7 整数反转 数组 Easy √ 12 整数反转 字符串 Medium √ 13 罗马数字转整数 散列表 Easy √ 15 三数之和 散列表 Medium √ 17 电话号码的字母组合 回溯法 Medium √ 19 删除链表的倒数第N个节点 ...