Python数据结构与算法05——二分查找

二分查找——递归版：

def binarySearch(aimlist, item):
    # 获取列表的长度
    n = len(aimlist)
    
    # 如果列表非空
    if n > 0:
        # 计算中间索引
        mid = n // 2
        
        # 如果中间元素是目标元素，则找到了
        if aimlist[mid] == item:
            return True
        # 如果中间元素小于目标元素，则在右半部分继续查找
        elif aimlist[mid] < item:
            # 递归调用并返回结果
            return binarySearch(aimlist[mid + 1:], item)
        # 如果中间元素大于目标元素，则在左半部分继续查找
        else:
            # 递归调用并返回结果
            return binarySearch(aimlist[:mid], item)
    else:
        # 列表为空，未找到目标元素
        return False

非递归：

def binarysearch(aimlist, item):
    # 获取列表的长度
    n = len(aimlist)
    
    # 初始化搜索范围的首尾索引
    first = 0
    last = n - 1
    
    # 在搜索范围内循环查找
    while first <= last:
        # 计算中间索引
        mid = (first + last) // 2
        
        # 如果中间元素是目标元素，则找到了
        if aimlist[mid] == item:
            return True
        # 如果中间元素小于目标元素，则在右半部分继续查找
        elif aimlist[mid] < item:
            first = mid + 1
        # 如果中间元素大于目标元素，则在左半部分继续查找
        else:
            last = mid - 1
    
    # 如果循环结束仍未找到目标元素，返回False
    return False