算法图解2-二分法和选择排序

# 非递归版本

def binary_search(alist, target):   
    low = 0    # 指定需要查找的范围
    high = len(alist) - 1
    
    while low <= high:  # 查找的条件：只要范围没有缩小到只包含一个元素，就检查中间的元素
        mid = (low + high) // 2  # 定位中间的元素，需要进行取整
        guess = alist[mid]
        
        if guess == target:  # 中间的元素恰好是目标值，直接输出索引mid
            return mid  # 返回索引
        if guess > target:  # 猜测的数字太大  
            high = mid - 1  # 将高位左移，减1
        else:  
            low = mid + 1  # 猜测数字过小，地位右移1位
     
    return None


# 递归版本
def binary_search(alist, item):
    n = len(alist)
    
    if n > 0:
        mid = // 2
        guess = alist[mid]
        if guess == item:
            return True
        elif guess > item:   # 猜测过大，要左移
            return binary_search(alist[:mid], item)  # 搜索的列表左移
        elif:
            return binary_search(alist[mid+1:], item)  # 猜测过小，搜索的列表右移
        
    return False

# 线性查找

def linear_search(alist, obj):
    n = len(alist)
    
    for i range(0, n):  # 遍历循环每个元素和目标元素进行比较
        if alist[i] == obj:
            return i 
     return "{} not in the alist".format(obj)

def findSmallest(alist):  # 找出最小的元素
    n = len(alist)
    
    smallest = alist[0]
    smallest_index = 0
    
    for i in range(1, n):  # 遍历数组中每个元素（除了第一个元素）
        if alist[i] < smallest:  # 如果数组其他的元素比第一个小，说明alist[i]更小
            smallest = alist[i]  # 赋值并且索引交换
            smallest_index = i
    return smallest_index  # 返回索引值，pop方法需要

def selectSort(arr):  # 选择排序
    newarr = []
    n = len(arr)
    
    for i in range(n):
        smallest = findSmallest(arr)  # 返回接收到的是索引
        newarr.append(arr.pop(smallest))  # pop默认删除最后一个元素，指定索引来删除元素，并且返回删除的值
    return newarr