二、搜索

1. 搜索

（1）顺序搜索

def search(num_list, val):
    if num_list == None:
        return -1
    
    for i in range(0, len(num_list)):
        if (num_list[i] == val):
            return i
    return -1

分析：时间复杂度为O(n)，空间复杂度O(1) 

(2) 二分搜索

A. 递归版本

def bi_search_re(num_list, val):
    def bi_search(l, h):
        
        if l > h:
            return -1
        
        mid = (l + h) // 2
        if (num_list[mid] == val): # 递归的base情况 
            return mid;
        elif (num_list[mid] < val): # 往右查找
            return bi_search(mid + 1, h)
        else: 
            return bi_search(l, mid - 1) # 往左查找
        
    return bi_search(0, len(num_list)-1)

B. 迭代版本

def bi_search_iter(alist, item):
    left, right = 0, len(alist) - 1
    while left <= right:
        mid = (left + right) // 2
        if alist[mid] < item: # 向右查找
            left = mid + 1
        elif alist[mid] > item: # 向左查找 
            right = mid - 1
        else: # alist[mid] = item 
            return mid
    return -1

分析：时间复杂度O(lgN)，空间复杂度O(1)，什么情况下适合此种方法？———>  数组前提是排好序的