`
OpenMind
  • 浏览: 179840 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

二分搜索专题2-在有序二维数组中搜索一个元素

阅读更多
1,设二维数组p的每行每列都按照下标递增的顺序递增。
用数学语言描述如下:p满足
(1),对任意的x1,x2,y,如果x1<x2,则p(x1,y)<p(x2,y);
(2),对任意的x,y1,y2, 如果y1<y2,则p(x,y1)<p(x,y2);
2,问题:
给定满足1的数组p和一个整数k,求是否存在x0,y0使得p(x0,y0)=k?
3,算法分析:
(1),穷举法,遍历二维数组,复杂度O(n*n),这个方法的代码我就不写了。
(2),二分搜索,复杂度为O(n*lgn),遍历每一行,每一列采用二分搜索。
	//n*O(lgn)
	public static Point search(int[][] p, int k) {
		for (int i = 0; i < p.length; i++) {
			int j = bSearch(p[i], 0, p[i].length, k);
			if (j > 0) {
				return new Point(i, j);
			}
		}
		return null;
	}
	/**
	 * 用二分算法搜索递增数组X下标从s到e区间的值为t的元素的下标
	 */
	public static int bSearch(int[] X, int s, int e, int t) {
		while (s <= e) {
			int m = (s + e) / 2;
			if (X[m] == t) {
				return m;
			} else if (X[m] > t) {
				e = m - 1;
			} else {
				s = m + 1;
			}
		}
		return -1;
	}
	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}


我猜想,应该存在O(lgn*lgn)的算法,暂时没有想到。
分享到:
评论

相关推荐

    课堂笔记06(二分查找-二维数组-数组的复制)共2页.pd

    二分查找,也被称为折半查找,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两半,然后比较中间元素与目标值,如果目标值等于中间元素,查找结束;如果目标值小于中间元素,则在左半部分数组中...

    将二维数组进行线性插值

    二维数组在计算机科学中,是一个多维数据结构,它由一串连续的内存位置组成,这些位置代表了按行和列排列的元素。每个元素可以通过一对索引(行索引和列索引)来访问。例如,一个二维数组可以表示为`arr[row][column...

    C语言教学课件:13-2_2_一维数组的应用(选择).ppt

    在C语言中,一维数组是一系列相同类型的数据元素的集合,它们在内存中连续存储。数组的定义和初始化是学习C语言的基础知识。 1. **数组定义**: 一维数组可以定义为 `类型名 数组名[大小]`,例如 `int arr[10];` ...

    js代码-二维数组中的查找

    上述代码中,`linearSearch二维数组`函数接受一个二维数组和一个目标值作为参数,返回一个对象,包含了目标值在数组中的位置(行和列)。如果未找到目标值,函数返回`null`。 另外,如果二维数组的每一行都是有序的...

    数组应用&二维数组.doc

    二维数组是指元素全部是一个一维数组的数组。 二维数组的定义:数据类型[][] 数组名 = new 数据类型[二维数组的容量][二维数组中一维数组的容量]; 二维数组的使用: * 声明一个二维数组:使用符号[][]表示 * 数据...

    二分查找 杨辉三角 数组便利

    从给定的代码片段中,我们可以提取出三个主要的知识点:二分查找算法、杨辉三角的生成以及一维和二维数组的操作。下面将详细解释这些知识点。 ### 二分查找算法 二分查找(Binary Search)是一种在有序数组中查找...

    2D-array-sort.zip_LabVIEW 数组_labview_labview array_perl sort arr

    在这个实验中,通过“二维数组快速排序.vi”,你可以学习如何在LabVIEW中设计交互式界面,如何处理2D数组,以及如何实现快速排序算法。同时,也可以了解到LabVIEW中的数据操作和控制流程,这对于提高LabVIEW编程技能...

    二维数组中的查找杂谈1

    本文主要讨论的是如何在一种特殊结构的二维数组中高效地查找特定元素。这种二维数组的特点是每一行从左到右递增排序,每一列从上到下也递增排序。这种问题通常出现在算法和矩阵相关的编程题目中,对算法设计和分析有...

    二维数组中的查找1

    二维数组中的查找问题是一个典型的二分搜索算法在二维空间的应用。在这个问题中,给定一个 n * m 的二维数组,数组的每一行都是从左到右递增的,每一列都是从上到下递增的。这样的数据结构类似于一个有序的矩阵,...

    Python 二维数组中的查找

    在Python编程语言中,二维数组是一种常见的数据结构,它由多个一维数组组成,形成一个矩阵状的结构。在这个特定的问题中,我们处理的是一个特殊类型的二维数组,其特点是每行从左到右递增,每列从上到下递增。这样的...

    ACM作业答案一维数组.rar

    一维数组是计算机科学中最基本的数据结构之一,它是一系列相同类型元素的有序集合,可以通过索引来访问和操作这些元素。数组在算法设计中扮演着重要角色,特别是在处理线性数据、查找和排序问题时。 1. **一维数组...

    编制一维数组排序程序。数组大小n用全局变量定义,数组数据从文本文件中读入或随机生成。包含冒泡排序、选择排序、插入排序三种排序方法。程序能够选择使用任何一种方法排序。

    一维数组是最简单的数据结构之一,它是一个有序的元素集合,每个元素通过索引访问。在编程中,一维数组通常用于存储线性数据,例如数字序列。数组的大小(n)在这里被定义为全局变量,这意味着在整个程序中都可以...

    一维数组教学设计.doc

    一维数组是C语言程序设计的基础,理解和熟练掌握一维数组的使用是后续学习二维数组、字符数组等更复杂数据结构的基础。通过有效的教学设计,将理论知识与实践操作相结合,能激发学生的学习兴趣,提高其编程能力,为...

    在数组中快速查找近似值

    在数组中快速查找近似值是一项常见的编程任务,特别是在数据处理和算法设计中。这个话题主要涉及两个核心概念:数组和近似值。数组是一种线性数据结构,它存储了一组相同类型的元素,并通过索引进行访问。近似值则是...

    查找数组中的数

    在C#中,数组可以是一维、二维或多维的,这里我们主要关注一维数组。一维数组的声明和初始化如下: ```csharp int[] numbers = new int[5]; // 声明一个包含5个整数的一维数组 numbers[0] = 1; // 给第一个元素赋值...

    8.二维数组和常见排序算法.doc

    在编程领域,数组是基础数据结构之一,而二维数组则是数组的一个扩展,它允许我们存储二维数据,就像表格一样。二维数组是由多个一维数组组成的,可以想象成一个矩阵或表格,每一行代表一个一维数组,列数则定义了每...

    Python实现二维有序数组查找的方法

    在Python编程中,二维有序数组查找是一个常见的问题,特别是在处理表格数据或矩阵时。本篇文章将深入探讨如何在二维有序数组中高效地查找特定元素。二维有序数组的特点是每一行和每一列都按照递增顺序排列,这为查找...

    4.一维数组.pptx

    在给定的代码示例中,有两个程序展示了如何使用一维数组处理数据。第一个程序使用了10个单独的变量`a1`到`a10`来存储成绩,这种方法在处理大量数据时显得繁琐。第二个程序则使用了一维数组`a[11]`,更简洁且易于理解...

    JS实现将二维数组转为json格式字符串操作示例

    在JavaScript中,二维数组是一个数组,它包含的每个元素本身也是一个数组。 在示例代码中,定义了两个二维数组arr和array。第一个二维数组arr被初始化为包含四个元素的一维数组,每个一维数组包含两个数字。第二个...

    数据结构_期末考试试卷_复旦大学计算机科学技术学院-2012(1)1

    1. **数组**:题目中提到了二维数组W,数组是一种线性数据结构,它以固定大小的同类型元素集合表示。数组的元素按特定顺序存储,可以通过下标访问。在本题中,数组W的每个元素占用4个字节,共有8行4列,所以总占用...

Global site tag (gtag.js) - Google Analytics