二分查找的变形我不会,最简单的查找某个元素我的位置我是会的。
二分查找的16种代码,即(第一个 >= > <= < target 的元素,共4种)(数组元素升序、降序,共2种)(左边界、右边界,共2种)== 16种不同的代码
要求:16种代码的模板,和记忆的方法(就是什么情况代码的哪个地方该怎么写)。
注意:代码用C/C++写,并且用循环实现,不要用递归。
二分查找是一种在有序数组中查找指定元素的算法,它的基本思想是:每次将查找区间缩小一半,直到找到目标元素或者确定目标元素不存在为止。
下面是两种写法:
递归版本
def binary_search(array, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return binary_search(array, target, low, mid-1)
else:
return binary_search(array, target, mid+1, high)
# 调用方法
index = binary_search(array, target, 0, len(array)-1)
循环版本
def binary_search(array, target):
low, high = 0, len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
# 调用方法
index = binary_search(array, target)
在这里,array 是待查找的有序数组,target 是要查找的元素,low 和 high 分别表示查找区间的左右端点。如果找到了目标元素,函数会返回其在数组中的下标;如果没有找到,函数会返回 -1。
追问你看看我问的是什么好吗,你学过C语言吗,这是你在网上找的?