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

yipeiwu_com6年前Python基础

本文实例讲述了Python实现二维有序数组查找的方法。分享给大家供大家参考,具体如下:

题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快。第一反应都是二分查找。对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路。

比较好的另一种思路是,首先选取数组右上角的数字,如果该数字等于要查找的数字,则查找结束;如果该数字大于要查找的数字,剔除这个数字所在的列,如果该数字小于要查找的数字,剔除这个数字所在的行。这样每一步都可以剔除一行或一列,查找的速度比较快。

python实现的代码:

# -*- coding:utf-8 -*-
'''
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
'''
def search(array, num):
  # 参数合法性判断忽略
  i = 0
  j = len(array[0]) - 1
  max_i = len(array) - 1
  while i <= max_i and j >= 0:
    if array[i][j] == num:
      return True
    elif array[i][j] > num:
      j = j - 1
    else:
      i = i + 1
  return False
if __name__ == '__main__':
  a = [[1, 2, 8, 9],
     [2, 4, 9, 12],
     [4, 7, 10, 13],
     [6, 8, 11, 15],
     ]
  print search(a, 14)
  print search(a, 7)
  print search(a, 0)

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

从零学Python之入门(四)运算

Python的运算符和其他语言类似 (我们暂时只了解这些运算符的基本用法,方便我们展开后面的内容,高级应用暂时不介绍) 数学运算 复制代码 代码如下:>>>print...

Python的Flask框架中集成CKeditor富文本编辑器的教程

CKeditor是目前最优秀的可见即可得网页编辑器之一,它采用JavaScript编写。具备功能强大、配置容易、跨浏览器、支持多种编程语言、开源等特点。它非常流行,互联网上很容易找到相关...

Python实现二叉树结构与进行二叉树遍历的方法详解

Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树的建立 使用类的形式定义二叉树,可读性更好 class BinaryTree: def __init__(self, root): self.key = ro...

Python 图像对比度增强的几种方法(小结)

Python 图像对比度增强的几种方法(小结)

图像处理工具——灰度直方图 灰度直方图时图像灰度级的函数,用来描述每个灰度级在图像矩阵中的像素个数或者占有率。 例子:矩阵 图片来自网络,侵删! 上面图片的灰度直方图 p...

Python中replace方法实例分析

本文以实例形式讲述了Python中replace方法,很有实用价值,具体如下: replace方法主要有两种: last_date = "1/2/3" 目标为"123" 方法一:repa...