Python查找数组中数值和下标相等的元素示例【二分查找】

yipeiwu_com5年前Python基础

本文实例讲述了Python查找数组中数值和下标相等的元素。分享给大家供大家参考,具体如下:

题目描述:

假设一个单调递增的数组中的每个元素都是整数并且是唯一的。请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组【-3,-1,1,3,5】中,3和他的下标相等。

采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标。如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找。

算法示例:

# -*- coding:utf-8 -*-
#! python3
class Solution:
  def numberEqualSubscript(self, numbers):
    if numbers == []:
      return -1
    left = 0
    right = len(numbers) - 1
    while(left <= right):
      middle = (left + right) >> 1
      if numbers[middle] == middle:
        return middle
      elif numbers[middle] < middle:
        left = middle + 1
      else:
        right = middle - 1
    return -1
numbers = [-3,-1,1,3,5]
print(Solution().numberEqualSubscript(numbers))

运行结果:

3

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

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

相关文章

python获取指定目录下所有文件名列表的方法

python获取指定目录下所有文件名列表的方法

本文实例讲述了python获取指定目录下所有文件名列表的方法。分享给大家供大家参考。具体实现方法如下: 这里python代码实现获取文件名列表的功能,可以指定文件中包含的字符,方便提取特...

python实现超市扫码仪计费

python实现超市扫码仪计费

python实现超市扫码仪计费的程序主要是使用超市扫码仪扫商品的条形码,读取商品信息,实现计费功能。主要用到的技术是串口通信,数据库的操作,需要的环境包括:python环境,mysql,...

对Python中的@classmethod用法详解

在Python面向对象编程中的类构建中,有时候会遇到@classmethod的用法。 总感觉有这种特殊性说明的用法都是高级用法,在我这个层级的水平中一般是用不到的。 不过还是好奇去查了一...

解决python2.7 查询mysql时出现中文乱码

问题: python2.7 查询或者插入中文数据在mysql中的时候出现中文乱码 --- 可能情况: 1.mysql数据库各项没有设置编码,默认为'latin' 2.使用MySQL...

python 三元运算符使用解析

三元运算又称三目运算,是对简单的条件语句的简写 简单条件语句: if 条件成立: val = 1 else: val = 2 改成三元运算: val = 1 if 条件...