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

赞 (0)

相关推荐

  • 使用python中的in ,not in来检查元素是不是在列表中的方法

    如果在列表中返回True ,否则返回False 以上这篇使用python中的in ,not in来检查元素是不是在列表中的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • 在Python中分别打印列表中的每一个元素方法

    Python版本 3.0以上 分别打印列表中的元素有两种: 方法一 a = [1,2,3,4] print(*a,sep = '\n') #结果 1 2 3 4 方法二 a = [1,2,3,4] [print(i) for i in a] #结果 1 2 3 4 [None, None, None, None] 以上这篇在Python中分别打印列表中的每一个元素方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Python 实现两个列表里元素对应相乘的方法

    方法一: 结合zip函数,使用map函数: List1 = [1,2,3,4] List2 = [5,6,7,8] List3 = map(lambda (a,b):a*b,zip(List1,List2)) print List3 方法二: 把列表转化为数组,使用np.multiply函数 List = [1,2,3] List2 = [5,6,7] List3 = np.multiply(np.array(List1),np.array(List2)) print List3.tolist(

  • python 获取list特定元素下标的实例讲解

    在平时开发过程中,经常遇到需要在数据中获取特定的元素的信息,如到达目的地最近的车站,橱窗里面最贵的物品等等.怎么办?看下面 方法一: 利用数组自身的特性 a.index(target), 其中a是你的目标list,target是你需要的下标对应的值 a=[72, 56, 76, 84, 80, 88] print(a.index(76)) output: 2 但是,如果a中有多个76呢? 我们发现,这种方法仅仅能获取都第一个匹配的value的下标(可以试试o_o) 所以,我们看看我们的第二种方案

  • python如何获取列表中每个元素的下标位置

    Git是编程中的基本技能之一,互联网公司几乎都在使用Git进行协作编程,昨天还有位禅友在微信上专门告诉我说星期五面试的时候刚好被问到 Git,幸好在这几天学了一下.Git并不难,但会Git至少可以说明一个人的学习能力或者说对技术的嗅觉能跟上主流,如果面试问你GitHub是什么都不知道,面试官就会对你打一个大的问号. 简单点评这一道题. 在使用 for 循环迭代一个列表时,有时我们需要获取列表中每个元素所在的下标位置是多少,例如 numbers = [10, 29, 30, 41],要求输出 (0

  • Python 查找list中的某个元素的所有的下标方法

    如下所示: #!/usr/bin/env python #_*_ coding:utf-8 _*_ name = ['hello', 'world', 'a', 'b', 'c', 1, 2, 3, 'hello', 'world', 'a', 'b', 'c', 1, 2, 3] first_pos = 0 for i in range(name.count(2)): new_list = name[first_pos:] next_pos = new_list.index(2) + 1 pr

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

    本文实例讲述了Python查找数组中数值和下标相等的元素.分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的.请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组[-3,-1,1,3,5]中,3和他的下标相等. 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标.如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找. 算法示例: # -*-

  • JS实现查找数组中对象的属性值是否存在示例

    JS实现查找数组中对象的属性值是否存在示例

    本文实例讲述了JS实现查找数组中对象的属性值是否存在.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> </head> <body> <script> var studentsArray = [ { "

  • python numpy数组中的复制知识解析

    这篇文章主要介绍了python numpy数组中的复制知识解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 vector = numpy.array([5, 10, 15, 20]) equal_to_ten_or_five = (vector == 10) | (vector == 5) vector[equal_to_ten_or_five] = 50 print(vector) 第一次看到这个的时候一脸懵逼,后来分析了下懂了下面记录下,

  • Python实现查找数组中任意第k大的数字算法示例

    本文实例讲述了Python实现查找数组中任意第k大的数字算法.分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索.与快排不同的是,每次都减少了一半的排序. def partitionOfK(numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end

  • Python实现找出数组中第2大数字的方法示例

    本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis

  • Python替换NumPy数组中大于某个值的所有元素实例

    我有一个2D(二维) NumPy数组,并希望用255.0替换大于或等于阈值T的所有值.据我所知,最基础的方法是: shape = arr.shape result = np.zeros(shape) for x in range(0, shape[0]): for y in range(0, shape[1]): if arr[x, y] >= T: result[x, y] = 255 有更简洁和pythonic的方式来做到这一点吗? 有没有更快(可能不那么简洁和/或不那么pythonic)的

  • 利用js查找数组中指定元素并返回该元素的所有索引示例

    前言 这篇文章主要给大家介绍的是利用js查找数组中指定元素并返回该元素的所有索引的相关资料,文中给出了详细的示例代码,下面话不多说,来看看详细的代码示例吧. 示例代码 //在数组中查找所有出现的x,并返回一个包含匹配索引的数组 function findall(a,x){ var results=[], len=a.length, pos=0; while(pos<len){ pos=a.indexOf(x,pos); if(pos===-1){//未找到就退出循环完成搜索 break; } r

  • JS查找数组中重复元素的方法详解

    JS查找数组中重复元素的方法详解

    本文实例讲述了JS查找数组中重复元素的方法.分享给大家供大家参考,具体如下: JS的数据类型有一个数组.今天我们就来谈谈对数组的一种处理.相信很多人都遇到过从数组中查找出不重复的元素,但是我遇到的却是从数组中查找出重复的元素. 从js数组中查找出不重复的元素的方法有很多,下面就给大家列举一个: <!DOCTYPE html> <html> <body> <script> Array.prototype.deleteEle=function(){ var ne

  • php数组函数序列之in_array() - 查找数组中是否存在指定值

    in_array()定义和用法 in_array() 函数查找数组中是否存在指定值. 语法 in_array(value,array,type)参数 描述 value 必需.规定要在数组搜索的值. array 必需.规定要搜索的数组. type 可选.如果设置该参数为 true,则检查搜索的数据与数组的值的类型是否相同. 说明 如果给定的值 value 存在于数组 array 中则返回 true.如果第三个参数设置为 true,函数只有在元素存在于数组中且数据类型与给定值相同时才返回 true.

  • PHP查找数组中只出现一次的数字实现方法【查找特定元素】

    本文实例讲述了PHP查找数组中只出现一次的数字实现方法.分享给大家供大家参考,具体如下: 问题: 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,b],其中ab是出现一次的两个数字 $count = array_count_values($array); foreach

随机推荐