Python二分查找详解

2024-04-05 20:11:09

先来看个实例

#!/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:
      print mid
      return mid
  print -1
  return -1 

if __name__ == "__main__":
  a = [int(i) for i in list(sys.argv[1])]
  m = int(sys.argv[2])
  search2(a,m)

运行:

administrator@ubuntu:~/Python$ python test_search2.py 123456789 4

注:

1.'__'：由于python的类成员都是公有、公开的被存取public，缺少像正统面向对象语言的私有private属性。
于是就用__来将就一下，模拟私有属性。这些__属性往往是内部使用，通常情况下不用改写。也不用读取。
加上2个下划线的目的，一是不和普通公有属性重名冲突，二是不让对象的使用者(非开发者)随意使用。
2.__name__ == "__main__"表示程序脚本是直接被执行的.
如果不等于表示脚本是被其他程序用import引入的.则其__name__属性被设为模块名

Python采用二分查找找出数字的下标

要考虑有重复数字的情况

class Solution(object):
  def searchRange(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    def binary_search(start,end,value):
      while end>=start:
        mid = (start+end)//2
        print(mid)
        if nums[mid]>target:
          end = mid-1
        elif nums[mid]<target:
          start = mid+1
        else:
          if value==-1:
            if mid-1>=start and nums[mid+value] == target:
              end = mid+value
            else:
              return mid
          else:
            if mid+1<=end and nums[mid+value] == target:
              start = mid+value
            else:
              return mid

      return -1
    a=binary_search(0,len(nums)-1,-1)
    b=binary_search(0,len(nums)-1,1)
    return [a,b]
a = Solution()
l = [2,2]
print(a.searchRange(l,2))

二分算法的定义不在多说了，百度一下就知道（支持国产大笑）

import sys
source = [1,2,3,4,5,6,7,8,9,10] #must be in order
des = int(sys.argv[1])
low = 0
high = len(source) - 1
targetIndex = -1
print "des=",des
while low <= high:
  middle = (low + high)/2
  if des == source[middle]:
    targetIndex = middle
    break
  elif des < source[middle]:
    high = middle -1
    print "middle element[index=",middle,",value=",source[middle],"] is bigger than des, continue search from[",low,"to",high,"]"
  else:
    low = middle + 1
    print "middle element[index=",middle,",value=",source[middle],"] is smaller than des, continue search from[",low,"to",high,"]"
print "search complete, target element's index in source list is ",targetIndex

最后在分享一个

'fileName--BinarySearch.py' 

src = [] 

def BinarySearch(low, high, target, *src):
  '二分查找'
  while low <= high:
    mid = (low + high) // 2
    midVal = src[mid]
    if target < midVal:
      high = mid - 1
    elif target > midVal:
      low = mid + 1
    else:
      return mid
    BinarySearch(low, high, target, *src) 

print('Please input 10 number:')
for number in range(10):
  src.append(int(input('Num %d:' % number))) 

sortList = tuple(src) 

key = int(input('Please input key:'))
location = BinarySearch(0, len(src) - 1, key, *sortList) 

if location != None:
  print('Find target at %d' % (location + 1))
else:
  print('No target!')

Python实现二分查找与bisect模块详解

前言其实Python 的列表(list)内部实现是一个数组,也就是一个线性表.在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n) .对于大数据量,则可以用二分查找进行优化. 二分查找要求对象必须有序,其基本原理如下: 1.从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: 2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. 3.如果在某一步骤数组为空,则代表找不到. 二分查找也
简介二分查找算法与相关的Python实现示例

二分查找Binary Search的思想: 以有序表表示静态查找表时,查找函数可以用二分查找来实现. 二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止. 1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n). 假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid = (low + high) / 2; 具体过程: 1.先将关键字与 mid 指向的元素比较,如果相
python实现二分查找算法

二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优
python二分查找算法的递归实现方法

本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite
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基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: 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二分查找详解

先来看个实例 #!/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: print mid return mid print -1 return -
python 二分查找和快速排序实例详解

思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e
Python 二分查找之bisect库的使用详解

目录简介 bisect 库的使用 bisect_left bisect_right insort_left insort_right 二分查找基础实现简介 bisect 库是 Python 标准库中的一部分,它提供了二分查找的功能.二分查找是一种在有序列表中查找某一特定元素的搜索算法.它的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),比顺序查找的时间复杂度 O ( n ) O(n) O(n) 要有效率. bisect 库的使用 bisect 库提供了 bise
Python操作MongoDB详解及实例

Python操作MongoDB详解及实例由于需要在页面展示MongoDB库里的数据,所以考虑使用python操作MongoDB,PyMongo模块是Python对MongoDB操作的接口包,所以首页安装pymongo. 1.安装命令 pip install pymongo 2.查询命令: import pymongo # 创建连接 client = pymongo.MongoClient(host="10.0.2.38", port=27017) # 连接probeb库 db = c
正则表达式+Python re模块详解

正则表达式(Regluar Expressions)又称规则表达式,在代码中常简写为REs,regexes或regexp(regex patterns).它本质上是一个小巧的.高度专用的编程语言. 通过正则表达式可以对指定的文本实现匹配测试.内容查找.内容替换.字符串分割等功能. re模块介绍 Python中的re模块提供了一个正则表达式引擎接口,它允许我们将正则表达式编译成模式对象,然后通过这些模式对象执行模式匹配搜索和字符串分割.子串替换等操作.re模块为这些操作分别提供了模块级别的函数
关于python类SortedList详解

目录 SortedList 有序序列方法 1.添加值 2.移除值 3.查找 4.迭代值 5. 其他 SortedList 有序序列 class sortedcontainers.SortedList(iterable=None, key=None) 方法 1.添加值 SortedList.add(value) 添加新元素,并排序.时间复杂度O(log(n)). SortedList.update(iterable) 对添加的可迭代的所有元素排序.时间复杂度O(k*log(n)). 2.移除值
Python 虚拟环境venv详解

目录什么是虚拟环境一句话总结为什么要虚拟环境说下背景了解下第三方库的安装目录带来的问题通过 venv 操作虚拟环境创建虚拟环境激活虚拟环境关闭虚拟环境 Pycharm 项目关联新创建的虚拟环境 Python Interpreter 选中虚拟环境安装项目所需要的库 Pycharm 创建虚拟环境查看虚拟环境的目录 bin include lib 从虚拟环境生成 requirement.txt 先看看有哪些包 pip freeze 包管理利器 popety 什么是虚拟环境这是
C语言数据结构之二分法查找详解

问题:在有序数组中查找给定元素的下标goal. 在查找一个数组元素的下标,可以用循环来解决,但是如果一个数足够大,比如说手机的价格,用循环来查找,就相当于叫一个人猜,从0开始,需要猜很久.这时候就出现了二分查找,也叫对半查找. 对半查找顾名思义就是猜一次,下次猜的内容就减少一半这时候定义一个变量left表示最左边元素的下标,在定义一个right表示最右边元素的下标,而mid就表示中间元素的下标. 当中间值小于目标值,left重新定义. if (mid < goal)
可能是史上最细的python中import详解

以前在使用import的时候经常会因为模块的导入而出现一些问题,以及一些似懂非懂半疑惑半糊涂的问题,索性花了点时间研究了一些python引用的方法,并且动手操作试验了一下,深有感触,特留此文以作总结,如有不当之处欢迎评论指正本文会尽我所能详细描述,字数会比较多,希望各位耐心看完. 首先我觉得应该先了解一下python的引用是怎么引用的我们首先新建一个python文件demo.py print(dir()) dir()命令是获取到一个object的所有属性,当传值为空时默认传入的是当前py文件
Python组合数据类型详解

目录集合元组创建方式列表操作函数操作方法列表的引用字典查找修改和添加字典的操作函数字典的操作方法集合创建集合有两种方式: 第一种: T = {11,111,"11"} print(T) # {'11', 111, 11} 第二种: T = set("Hello Would") print(T) {'H', 'e', 'o', ' ', 'l', 'd', 'u', 'W'} 注意: 1.如果创建空集合必须使用第二种方法. 2.集合中元素

Python二分查找详解

相关推荐

随机推荐