跳到主要内容

简述简单实现简单二分搜索 ?

参考答案:

二分搜索(也称为二分查找)是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索过程结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

以下是一个简单的二分搜索的Python实现:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None

# 测试
my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))  # 输出: 1
print(binary_search(my_list, -1))  # 输出: None

这个函数接受一个有序数组(arr)和一个目标值(target)作为参数。然后,它初始化两个指针,一个指向数组的开始(low),另一个指向数组的结束(high)。在每一步中,它计算中间索引(mid),然后检查该索引处的值(guess)是否等于目标值。如果是,函数返回该索引。如果guess大于target,则目标值必须在数组的左半部分,因此将high设置为mid - 1。否则,目标值必须在数组的右半部分,因此将low设置为mid + 1。如果low大于high,则说明数组中不存在目标值,函数返回None

学习笔记
|||
说点什么吧
 
100:0
鲤跃网
http://www.sunycode.com
讲文明、要和谐
提交学习笔记
0 学习笔记
  • 还没有学习笔记,快来抢沙发吧!