python中二分查找法的实现方法

如果想要在有序数据中进行查找想要的数据，二分查找法就个好方法，它可以大大缩短了搜索时间，是一种常见的查找方法。二分查找很好写，却很难写对，下面，小编就简单向大家介绍一下二分查找，并演示器使用代码。

1、二分查找

在一个有序并且无重复的列表中，对该列表的元素进行查找。

2、特点

（1）必须针对于有序列表

（2）该列表必须无重复

（3）按下标索引查找

3、使用方法

非递归实现：

def binary_search(alist, item):
  """二分查找 非递归方式"""
  n = len(alist)
  start = 0
  end = n - 1
  while start <= end:
    mid = (start + end) // 2
    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      end = mid - 1
    else:
      start = mid + 1
  return False

if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

递归实现：

def binary_search_2(alist, item):
  """二分查找 递归方式"""
  n = len(alist)
  if 0 == n:
    return False
  mid = n // 2
  if alist[mid] == item:
    return True
  elif item < alist[mid]:
    return binary_search_2(alist[:mid], item)
  else:
    return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

基础知识点扩展：

介绍

二分查找也称折半查找（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]

到此这篇关于python中二分查找法的实现方法的文章就介绍到这了,更多相关python中二分查找法如何实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++二分查找算法实例

    本文实例为大家分享C++二分查找算法,通过改变边界位置来进行查找的方法,代码如下: #include <iostream> using namespace std; int search(int *p,int length,int key); int search1(int *p,int length,int key); int main() { cout << "Hello world!" << endl; int a[] = {1,2,3,4,5

  • Python如何实现的二分查找算法

    先来看个用Python实现的二分查找算法实例 import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -1 if _

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • Pythonic版二分查找实现过程原理解析

    前提:升序数组,待查元素在数组中. 二分查找:就是一个递归函数c.待查元素a,当前数组中位数b,如果b=a则返回b的索引,b>a则在b左侧的子数组中调用函数c,否则在b右侧子数组中调用函数c. 第一次思考,按着上面的思路编程后的结果: def binary_search(index, a, value): if a[(len(a) - 1) // 2] == value: return index + (len(a) - 1) // 2 elif a[(len(a) - 1) // 2] <

  • C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x) { asse

  • c++与python实现二分查找的原理及实现

    c++与python实现二分查找的原理及实现

    目录 1.时间复杂度与优缺点 2.python实现 3.C++实现 在计算机中,数据的查找方式与其存储方式关系密切.试想一下,如果图书馆中书籍杂乱无章的存放,那么要想找到心仪的书籍将会非常困难.为此,人们常常将物品按照某种规则或次序进行放置,目的是便于日后的查找. 作为查找算法家族中的一员,二分查找正是利用数据按次序存储这一优点,极大的提升了查找目标值所在位置的速度. 二分查找的核心思想是:首先将数组中间值和目标值进行比较,如果相等则返回:如果不相等,则选择中间值左边的一半或者右边的一半进行比较

  • 查找算法之二分查找的C++实现

    二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置. 前提:线性表中的记录必须是关键字有序(通常从小到大),线性表必须采用顺序存储. 基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:否则,在右半区查找.不断重复,直到查找成功或查找失败为止. #include<ios

  • C++二分查找(折半查找)算法实例详解

    本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复

  • python中二分查找法的实现方法

    如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法.二分查找很好写,却很难写对,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码. 1.二分查找 在一个有序并且无重复的列表中,对该列表的元素进行查找. 2.特点 (1)必须针对于有序列表 (2)该列表必须无重复 (3)按下标索引查找 3.使用方法 非递归实现: def binary_search(alist, item): """二分查找 非递归方式"

  • Python基于二分查找实现求整数平方根的方法

    本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

  • Python中的对象，方法，类，实例，函数用法分析

    本文实例分析了Python中的对象,方法,类,实例,函数用法.分享给大家供大家参考.具体分析如下: Python是一个完全面向对象的语言.不仅实例是对象,类,函数,方法也都是对象. 复制代码 代码如下: class Foo(object):     static_attr = True     def method(self):         pass foo = Foo() 这段代码实际上创造了两个对象,Foo和foo.而Foo同时又是一个类,foo是这个类的实例. 在C++里类型定义是在编

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

  • 在Python中表示一个对象的方法

    在 Python 中一切都是对象.如果要在 Python 中表示一个对象,除了定义 class 外还有哪些方式呢?我们今天就来盘点一下. 0x00 dict 字典或映射存储 KV 键值对,它对查找.插入和删除操作都有比较高效率.用一个 dict 对象可以非常容易的表示一个对象. dict 的使用也 很灵活,可以修改.添加或删除属性. >>> student={ 'name':'jack', 'age':18, 'height':170 } >>> student {'n

  • 在 Python 中使用 MQTT的方法

    Python 是一种广泛使用的解释型.高级编程.通用型编程语言.Python 的设计哲学强调代码的可读性和简洁的语法(尤其是使用空格缩进划分代码块,而非使用大括号或者关键词).Python 让开发者能够用更少的代码表达想法,不管是小型还是大型程序,该语言都试图让程序的结构清晰明了. MQTT 是一种基于发布/订阅模式的 轻量级物联网消息传输协议 ,可以用极少的代码和带宽为联网设备提供实时可靠的消息服务,它广泛应用于物联网.移动互联网.智能硬件.车联网.电力能源等行业. 本文主要介绍如何在 Pyt

  • 详解C语言中二分查找的运用技巧

    详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • Python中的list.sort()方法和函数sorted(list)

    目录 1.sort()方法 2.sorted()函数 3.可选参数 4.优先级排序 5.闭包修改标志变量 6.闭包修改标志变量2, 新增nonlocal sorted的关键字排序 1.sort()方法 sort()是列表的方法,修改原列表使得它按照大小排序,没有返回值,返回None In [90]: x = [4, 6, 2, 1, 7, 9] In [91]: x.sort() In [92]: x Out[92]: [1, 2, 4, 6, 7, 9] In [98]: aa = x.sor

  • python中列表元素连接方法join用法实例

    本文实例讲述了python中列表元素连接方法join用法.分享给大家供大家参考.具体分析如下: 创建列表: >>> music = ["Abba","Rolling Stones","Black Sabbath","Metallica"] >>> print music 输出: ['Abba', 'Rolling Stones', 'Black Sabbath', 'Metallica']

随机推荐