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

二分法查找

猜数字游戏

0-1000猜数字游戏：

• 普通查找：100,99,98,…,1，需要100步

• 二分法查找：100--->50--->25--->13--->7--->4--->2--->1，每次猜测中间的数字（假设猜测数字是1），将余下的数字排除一半。需要7步

n个元素组成的列表，最多需要走$log_2{n}$步。普通查找n步

attention：二分法查找仅对有序列表有用

思想

折半查找，比较次数少，速度快，只能作用于有序数组和顺序表，当查找范围内只有一个数据的时候，结束查找。

• 最优时间复杂度：$O(1)$
• 最坏时间复杂度：$O(logn)$

运行时间

运行时间是通过大o()运行时间来表示

• 二分查找的速度比线性查找快的多，元素越多，快的越多
• 算法运行时间是从其增速的角度来度量的

Python实现

# 非递归版本

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