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程序设计有所帮助。

相关文章

Windows平台Python编程必会模块之pywin32介绍

Windows平台Python编程必会模块之pywin32介绍

在Windows平台上,从原来使用C/C++编写原生EXE程序,到使用Python编写一些常用脚本程序,成熟的模块的使用使得编程效率大大提高了。 不过,python模块虽多,也不可能满足...

python实现bitmap数据结构详解

python实现bitmap数据结构详解

bitmap是很常用的数据结构,比如用于Bloom Filter中;用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二...

python time模块用法实例详解

本文详细讲述了python的内嵌time模块的用法。分享给大家供大家参考之用。具体分析如下:   一、简介 time模块提供各种操作时间的函数 说明:一般有两种表示时间的方式...

Python文件打开方式实例详解【a、a+、r+、w+区别】

本文实例讲述了Python文件打开方式。分享给大家供大家参考,具体如下: 第一步 排除文件打开方式错误: r只读,r+读写,不创建 w新建只写,w+新建读写,二者都会将文件内容清零 (以...

Python实现获取邮箱内容并解析的方法示例

本文实例讲述了Python实现获取邮箱内容并解析的方法。分享给大家供大家参考,具体如下: # -*- coding: utf-8 -*- from email.parser impo...