python二分法查找实例代码
作者:栾沫 发布时间:2022-08-28 17:25:25
标签:python,二分,查找
对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表
二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然,最好的情况是只查找一次就能找到,但是在最坏和一般情况下的确要比顺序查找好了很多。
题目一:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
class Solution:
def search(self,nums:List[int],target:int)->int:
left=0
right=len(nums)-1
while(left<=right):
mid=(left+right)//2
if nums[mid]==target:
return mid
if nums[mid]<target:
left=mid+1
else:
right=mid-1
return -1
题目二:在一个严格递减的数组中,找到第二个比目标值target大的数的下标。若不存在,则返回-1。
class Solution:
def search(self,nums:List[int],target:int)->int:
left=0
right=len(nums)-1
while(left<=right):
mid=(left+right)//2
if nums[mid]==target:
return mid
if nums[mid]>target:
left=mid+1
else:
right=mid-1
return -1
题目三:函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)-1):
left=i
right=len(numbers) - 1
while(left<=right):
mid=(left+right)//2
if numbers[mid]+numbers[i]==target:
return [i+1,mid+1]
elif numbers[mid]+numbers[i]<target:
left=mid+1
else:
right = mid-1
return [-1,-1]
来源:https://blog.csdn.net/weixin_51458838/article/details/121432897
0
投稿
猜你喜欢
- 在已有的shapefile文件的基础上增加字段: # -*- coding:gb2312 -*-import shapefiler=shap
- 文字向下滾動,逐渐隐藏效果~ 挺好的 <!DOCTYPE html PUBLIC "-//W3C//DTD XHT
- 这篇文章主要介绍了Python hashlib常见摘要算法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 1、删除Oracal在注册表中的主项:regedit.exe->LocalMachine->Software->Oracl
- </pre><pre name="code" class="javascript"
- 本文实例讲述了PHP实现的XXTEA加密解密算法。分享给大家供大家参考,具体如下:<?php/** * Xxtea 加密实现类 */c
- 两组字符串数据,需要比较其中相同的数据,并将其值相加并组成一个新的字符串数据a1="sp2=20;sp1=34;"a2=
- 本文实例讲述了Python实现计算文件MD5和SHA1的方法。分享给大家供大家参考,具体如下:不多说,直接源码:#file md5impor
- 一、网络请求在uni中可以调用uni.request方法进行请求网络请求需要注意的是:在小程序中网络相关的 API 在使用前需要配置域名白名
- 工程结构views.pydef home(request): TutorialList = ["HTML",
- 前几天同学要我帮他做个国际聊天室,要求能够将聊天的内容自动翻译成多国语言.本来想用worldlink的翻译服务,但是用ajax很难获得结果,
- 本文实例讲述了python处理二进制数据的方法。分享给大家供大家参考。具体如下:#!/usr/env/env python #-*- cod
- 本文实例讲述了js对象基础用法。分享给大家供大家参考。具体分析如下:js对象在本质上与数组相同,都是存放一组数据。但创建方法有所不同,对象需
- 在学习 Python 类的时候,会碰见类中有 __init__() 这样一个函数,其实它就是 Python 的构造方法。构造方法类似于类似
- 是的,我在这里要说:注册表单将死(好拗口啊,但是不知道怎么翻译更恰当)。回想一下,当你想享受一个网站服务的时候,碰到的第一件事是什么?一个表
- 列表生成式语法:[x*x for x in range(0,10)] //列表生成式,这里是中括号//结果 [0, 1, 4, 9, 16,
- asp代码 如下:读取注册表信息使用了对象WScript.Shell<%Dim strPath strP
- 在并不知道DIV浮动层的宽度,高度的情况下,如何使浮动层在任何分辩率的情况下居中呢! 下面使用了JAVASCRIPT来
- 目录while语句if 语句for语句BreakContinuePass流程控制无非就是if else之类的控制语句,今天我们来看一下Pyt
- 在CSS中我们会经常要用到“清除浮动”Clear,比较典型的就是clear:both;CSS手册上是这样说明的:该属性的值指出了不允许有浮动