二分法常见的应用(python版)

二分法常见的应用(python版) 二分法介绍

二分法作为基础性算法，在实际工程中也得到了广泛的应用。其计算时间复杂度为O(logN)，额外空间复杂度O(1)。整体算法由于其每次搜索对半砍的思想，使得其时间复杂度相较于暴力的遍历搜索O(N)变为以2为底的O(logN)。全程搜索只需要记录几个变量值，所需空间复杂度也大大减少变为O(1)。
下面首先展示下计算复杂度为O(N)的遍历搜索

import random 

data = sorted(random.sample([i for i in range(50)],20))
print(data)
# 判断一个数字是否在该数组中
# 遍历
def Search(data,num=10):
	for index,key in enumerate(data):
		if key == num:
			return key,index
	return -1

print(Search(data))

二分法常见的应用 问题1：在递增数组中判断某一数字是否存在，若存在返回位置

def Binarysearch(data,num=43,low=0,high=len(data)-1):
	"""如果该数字存在，则当low==high时便找到该数字，否则便不存在此数。每次只改变一侧的范围"""
	while low<=high:
		middle = (low+high)//2
		if data[middle]==num:return data[middle],middle
		elif data[middle] 
# 递归法
def Binarysearch1(data,num=49,low=0,high=len(data)-1):
	"""递归的递归结束条件最关键，分为两块。
	1：该数存在正常的返回条件
	2：概述不存在，索引结束的退出条件"""
	if low>high:return -1
	if data[low]==num:return data[low],low
	middle = (low+high)//2
	if data[middle] 
问题2 ：找出有序数组中满足某一条件的最左侧数字位置(数组中数字可以重复) 
data = [0,0,1,1,1,2,2,2,3,3,3,3,3,3,4,6,7]
print(data)

def LowerBound(data,num,low=0,high=len(data)-1):
	"""此时不需要low==high此条件，我们不需要知道该数字究竟在不在数组中，只要找到最左边比他大的数字即可"""
	while low 
def LowerBound1(data,num,low=0,high=len(data)-1):
"""递归的两个结束条件，一个正常退出，一个无满足条件退出条件"""
	if data[low]>=num:return data[low],low
	elif low>=high:return -1
	middle = (low+high)//2
	if data[middle] 
问题3 ：找出该数组中满足某一条件数值的相邻上边界(最左侧大于该数值的那个数) 
def UpperBound(data,num,low=0,high=len(data)-1):
	while low 
def UpperBound1(data,num,low=0,high=len(data)-1):
"""注意递归的退出条件"""
	if data[low]>num:return data[low],low
	elif low>=high:return -1
	middle = (low+high)//2
	if data[middle]<=num:
		low = middle+1
		return UpperBound1(data,num,low,high)
	else:
		high = middle
		return UpperBound1(data,num,low,high)
		
print(UpperBound1(data,num=1))
 
问题4：找出一个山峰式数组的peak(数组山峰两侧不会出现连续相等的数值) 
该类题目表面看起来是一个无序的列表，众所周知。我们二分法针对于处理一些有序数组，因此我们的核心思想是通过一种映射使其成为一种有序数组形式。我们可以在其中设定一个阈值，就像信号系统中的阶跃现象一样，如sign函数，或是深度学习中sigmoid函数那种有序的函数性质。
 
data = [0,1,2,3,4,5,6,7,8,3,2,1,0]
print(data)
"""我们其实可以将其转化为[-1，-1，-1，-1，-1，-1，-1,0，1,1，1,1]的有序形式，这样就相当于求最左侧满足条件的数字，套用上面的LowerBound函数形式就可。
另一个问题就是如何来映射这个关系，最直接的方式就再定义一个映射函数即可
"""
def custom_sort(data,i):
"""映射函数"""
	if data[i]>data[i-1] and data[i]>data[i+1]:return 0
	elif data[i]>data[i-1] and data[i]>1
		# middle = low+((high-low)>>1)
		num = custom_sort(data,middle)
		if num<0:
			low = middle+1
		else:
			high = middle
	return data[low],low

print(search_peak(data))
 
问题5：找一个山谷数字(举一反一) 
data = [6,5,3,2,1,0,-1,1,3,5,7,8,9]
print(data)

def custom_sort(data,i):
	if data[i]data[i+1]:return -1
	else:return 1

def search_vally(data,low=1,high=len(data)-2):
	while low 
补充小技巧 
之前没有接触过数据结构与算法，最近在学习中了解到一些挺有用的小技巧，特此记录一下。
 1：交换两个数字大小
 法1：
 tmp = a
 a = b
 b = tmp
 法2：异或（需要保证两个变量不在同一处内存地址，否则将会被抹去）
 a = a^b
 b = a^b
 a = a^b
 
2：位运算
 
    
     
      
       
        x
       
       
        >
       
       
        >
       
       
        n
       
       
        （
       
       
        x
       
       
        左
       
       
        移
       
       
        n
       
       
        位
       
       
        ）
       
       
        ，
       
       
        相
       
       
        当
       
       
        于
       
       
        x
       
       
        /
       
       
        /
       
       
        (
       
       
        
         2
        
        
         n
        
       
       
        )
       
      
      
       x>>n（x左移n位），相当于x//(2^n)
      
     
    x>>n（x左移n位），相当于x//(2n)
 
    
     
      
       
        x
       
       
        <
       
       
        <
       
       
        n
       
       
        （
       
       
        x
       
       
        右
       
       
        移
       
       
        n
       
       
        位
       
       
        ）
       
       
        ，
       
       
        相
       
       
        当
       
       
        于
       
       
        x
       
       
        ∗
       
       
        (
       
       
        
         2
        
        
         n
        
       
       
        )
       
      
      
       x<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5521354.html