欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python实现基础二分查找与二分查找的变形以及应用

程序员文章站 2024-03-19 21:40:46
...
  • 二分查找基础版本的递归与非递归
'''
	使用递归和非递归实现二分查找

	Author by: Lofues
'''

def binary_search(a : list, n : int, val : int) -> int:
	#return Binary_search(a,0,n-1,val)
	return binary_search_rec(a,0,n-1,val)

def Binary_search(a : list, low : int, high : int, val: int) -> int:
	while low <= high:
		mid = low + (high - low) // 2
		if a[mid] == val:
			return mid
		elif val < a[mid]:
			high = mid - 1
		else:
			low = mid + 1
	return -1

def binary_search_rec(a : list, low : int, high : int, val : int) -> int:
	if low > high: return -1
	mid = low + (high - low) // 2
	if a[mid] == val:
		return mid
	elif val < a[mid]:
		high = mid - 1
		return binary_search_rec(a,low,high,val)
	else:
		low = mid + 1
		return binary_search_rec(a,low,high,val)


a = [x for x in range(0,50,2)]
print(binary_search(a,50,21))
  • 二分查找的变形问题
'''
	解决二分查找的第一种变形问题: 
	1.找到第一个相同元素下标
	2.找到一个最后一个相同元素的下标
	3.找到第一个大于等于该元素的下标
	4.找到最后一个小于等于该元素的下标

	Author by: Lofues
'''

def binary_search(a : list, n : int, val : int) -> int:
	return Binary_search_find_the_first(a,0,n-1,val)
	#return Binary_search_find_the_last(a,0,n-1,val)
	#return Binary_search_find_the_first_ge(a,0,n-1,val)
	#return Binary_search_find_the_last_let(a,0,n-1,val)



def Binary_search_find_the_first(a : list, start : int, end : int, val : int) -> int:
	if start > end: return -1
	low,high = start,end
	while low <= high:
		mid = low + (high - low) // 2
		if val < a[mid]:
			high = mid - 1
		elif val > a[mid]:
			low = mid + 1
		else:
			# 如果相等元素是数组第一个元素或者前边一个元素不为val则返回
			if mid == start or a[mid-1] != val: return mid
			high = mid - 1
	return -1


def Binary_search_find_the_last(a: list, start : int, end : int, val : int) -> int:
	if start > end: return -1
	low,high = start,end
	while low <= high:
		mid = low + (high - low) // 2
		if val < a[mid]:
			high = mid - 1
		elif val > a[mid]:
			low = mid + 1
		else:
			# 如果相等元素是数组最后一个元素或者后边的一个元素不为val则返回
			if mid == end - 1 or a[mid+1] != val: return mid
			low = mid + 1
	return -1

def Binary_search_find_the_first_ge(a : list, start : int, end : int, val : int) -> int:
	# 找到第一个大于等于该元素的index
	if start > end: return -1
	low,high = start,end
	while low <= high:
		mid = low + (high - low) // 2
		if a[mid] >= val:
			if mid == start or a[mid - 1] < val:
				return mid
			else:
				high = mid - 1
		else:
			low = mid + 1
	return -1

def Binary_search_find_the_last_le(a : list, start : int, end : int, val :int) -> int:
	if start > end: return -1
	low,high = start,end
	while low <= high:
		mid = low + (high - low) // 2
		if a[mid] <= val:
			if mid == end - 1 or a[mid + 1] > val:
				return mid
			else:
				low = mid + 1
		else:
			high = mid - 1
	return -1
			

def main():
	a = [1,1,1,1,2,3,4,5,6,6,6,6,7,7,9,10]
	print(binary_search(a,len(a),8))
	print(a[13])

if __name__ == '__main__':
	main()
  • 利用二分查找求平方根
'''
	用二分查找方法查找一个数的平方根,误差不小于e-7

	Author by : Lofues
'''
def get_sqrt(n : int) -> float:
	if n < 0: return None
	precison = 1e-7
	low, high = 0, n
	while high - low >= precison:
		mid = low + (high - low) / 2
		if mid * mid < n:
			low = mid
		elif mid * mid > n:
			high = mid
		else: 
			return mid 
	return high 


print(get_sqrt(2))