折半查找-Python版(二分查找)

林末 等级 666 0 0

介绍

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

前提

必须待查找的序列有序

时间复杂度

O(log2n)

原理

1)确定该期间的中间位置K 2)将查找的值t与array[k]比较,若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。 3)区域确定过程: 若array[k]>t,由于数组有序,所以array[k,k+1,……,high]>t;故新的区间为array[low, ..., K-1]; 反之,若array[k]<t对应查找区间为array[k+1, ..., high]

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2021-03-02
# @Author  : 林末
# @desc : 二分查找算法,python版

def serach(array, t):
    array.sort() #排序,保证列表是有序的
    low = 0
    height = len(array) - 1
    while low <= height:
        k = (low + height) // 2
        if array[k] < t:
            low = k + 1
        elif array[k] > t:
            height = k - 1
        else:
            return k #找到后返回位置
    return -1 #找不到返回-1
array = [1, 3, 5, 7, 9, 6, 8, 0]
print(serach(array, 5))

End

林末:https://www.helloworld.net/linmo

收藏
评论区

相关推荐

Python的环境搭建和下载
Python是一个跨平台、可移植的编程语言,因此可在windows、Linux和Mac OS X系统中安装使用。 安装完成后,你会得到Python解释器环境,可以通过终端输入python命令查看本地是否已经按照python以及python版本。这里有一点需要注意的是,如果没有将python的安装目录添加到环境变量中,会报错(python不是内部命令或外部命
python的学习难?你的方法不对罢了,看看我的。
1、选择Python版本对于使用python的人来说,python的版本就是我们的工作环境,因此,在学习之前需要考虑好学习哪个版本,python2和python3的版本不同,会存在一些差异,虽说不大,但直接学习python3 的话相对来说会好一点,而且跑一趟还能3相对来说对零基础的小白来说更加的友好,容易上手。2、学习Python基础知识Python 是一个
python3.6虚拟环境以及flask的安装(常见问题)
准备基于python进行web应用开发 Python3.3以上的版本通过venv模块原生支持虚拟环境,可以代替Python之前的virtualenv。 该venv模块提供了创建轻量级“虚拟环境”,提供与系统Python的隔离支持。每一个虚拟环境都有其自己的Python二进制(允许有不同的Python版本创作环境),并且可以拥有自己独立的一套Python包
Ubuntu 常用命令记录
一、Python相关设置 ------------ 修改Python默认版本 ------------ cd /usr/bin sudo rm -rf python sudo ln -s /usr/bin/python3 /usr/bin/python 检查是否设置成功: python -V 安
CentOS升级Python到2.7版本
查看python的版本 python -V Python 2.4.3 1.先安装GCC yum -y install gcc 2.下载Python-2.7.2 wget http://python.org/ftp/python/2.7.2/Python-2.7.2.tar.bz2 3.解压Python-2.7.2
Centos升级Python 2.7.12并安装最新pip
Centos系统一般默认就安装有Python2.6.6版本,不少软件需要2.7以上的,通过包管理工具安装不了最新的版本,通过源码编译可以方便安装指定版本,只需要把下面版本的数字换成你想要的版本号。 #### 1.安装步骤 下载源码 1 wget http://www.python.org/ftp/python/2.7.12/Python-2.7.12
Django 2.0.3安装
OS:Windows 10家庭中文版,CPU:Intel Core i5-8250U Python版本:Python 2.7,Python 3.6 Django版本:2.0.3(最新2.0.5) **解压工具:7-zip 64位版** 目标:将Django 2.0.3安装到Python 3.6 在看了一些文章后,发现安装Django的方式有两种:基
Hadoop streaming使用自定义python版本和第三方库
在使用Hadoop的过程中,遇到了自带python版本比较老的问题. 下面以python3.7为例,演示如何在hadoop上使用自定义的python版本以及第三方库. 1.在https://www.python.org下载Python-3.7.2.gz包 2.在linux环境下: tar -xvf Pthon-3.7.2 #解压文件
Mac 升级Python 2.7 到 Python 3.7
MAC上默认内置安装了Python 2.7,但是Python 2.7到2020年就会停止维护了,并且有时候会出现依赖库的不兼容问题,那么怎么安装Python 3.X,并且将Python 3.X的版本设置为默认版本呢? ### 安装Python 3.7 有两种安装方式。 第一种是直接下载python3安装包安装: 1、下载地址如下:[https://w
Python 3 教程
Python 3 教程 =========== ![python3](https://www.runoob.com/wp-content/uploads/2014/05/python3.png) Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,
Python01 VSCode开发环境和入门程序
1、Python的下载和安装 -------------- 最新版本python3.7.3 [https://www.python.org/downloads/release/python-373/](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.python.org%2Fdo
Python升级Linux
CentOS 7 中默认安装了 Python,版本比较低(2.7.5),为了使用新版 3.x,需要对旧版本进行升级。 由于很多基本的命令、软件包都依赖旧版本,比如:yum。所以,在更新 python 时,建议不要删除旧版本(新旧版本可以共存)。 查看 Python 版本号 ============= 当 Linux 上安装 Python 后(默认安装)
Python安装Oracle数据库驱动
**1.环境设置** \[root[@oracle](https://my.oschina.net/oracle) ~\]# cat /etc/redhat-release  CentOS release 6.9 (Final) \[root[@oracle](https://my.oschina.net/oracle) ~\]# python -V
Python语言程序设计基础(第2版)课后习题答案 嵩天、礼欣、黄天羽版 高等教育出版社 试题和答案和解析
**Python语言程序设计基础(第2版)课后习题答案  嵩天、礼欣、黄天羽版 高等教育出版社 试题和答案和解析 复习提纲** **![](https://oscimg.oschina.net/oscnet/dd95fc8fbb6927d4e71067806fc01912bcd.jpg)** **Python语言程序设计基础(第2版)** **完整版答
Python资源大全中文版
### 环境管理 管理 Python 版本和环境的工具 * p:非常简单的交互式 python 版本管理工具。[官网](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fgithub.com%2Fqw3rtman%2Fp) * pyenv:简单的 Python 版本管理工具。[官网