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下自己编写web框架的一些要点

在正式开始Web开发前,我们需要编写一个Web框架。 为什么不选择一个现成的Web框架而是自己从头开发呢?我们来考察一下现有的流行的Web框架: Django:一站式开发框架,但不...

Python实现快速排序的方法详解

本文实例讲述了Python实现快速排序的方法。分享给大家供大家参考,具体如下: 说起快排的Python实现,首先谈一下,快速排序的思路: 1、取一个参考值放到列表中间,初次排序后,让左侧...

Pycharm新手教程(只需要看这篇就够了)

Pycharm新手教程(只需要看这篇就够了)

pycharm是一款高效的python IDE工具,它非常强大,且可以跨平台,是新手首选工具!下面我给第一次使用这款软件的朋友做一个简单的使用教程,希望能给你带来帮助! 目前pycha...

Python复制Word内容并使用格式设字体与大小实例代码

简介 网上流传的部分可以百度关键词“Python”和“word”后查看文章学习,以下内容为个人实践,修正了不能运行出错的情况。 代码示例 import win32com from...

python使用xmlrpclib模块实现对百度google的ping功能

本文实例讲述了python使用xmlrpclib模块实现对百度google的ping功能。分享给大家供大家参考。具体分析如下: 最近在做SEO的时候,为了让发的外链能够快速的收录,想到了...