查找算法（一）：查找

基于有序列表的查找。

线性查找

def search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

二分查找

二分查找（也称为折半查找），在给定一个有序数组的前提下，取中间的元素（arr[mid]）作为比较的对象，如果target值大于中间元素，则在中间元素的右边继续查找，反之，则在中间元素的左边继续查找。

def binary_search(arr, target):
    lo = 0
    hi = len(arr)-1
    
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            hi = mid - 1
        else:
            lo = mid + 1
            
    return -1

斐波那契数列查找

斐波那契数列公式：

$$F(n) = F(n-1) + F(n-2)$$

斐波那契查找步骤如下：

第一步：从斐波那契数列中找到第一个大于或等于数组长度（n）的数（fibM）

第二步：当数组中还有未遍历的元素时：

 1. 将游标cur定义为fib2覆盖部分的最后一个元素
 2. 比较目标值与arr[cur]进行比较，如果匹配，立即返回索引，完成查找
 3. 如果目标值大于arr[cur]，则把斐波那契数列下降一个单位
 4. 如果目标值小于arr[cur]，则把斐波那契数列下降两个单位

第三步：如果仅余一个元素用于比较，检验fib1是否等于1，如果是，判断该元素是否为target

def fibMonaccianSearch(arr, target, n): 
    # f(n) = f(n-1) + f(n-2)  
    # fib2 + fib1 = fibM
    # fib2 --> fib1 --> fibM
    fib2 = 0  
    fib1 = 1 
    fibM = fib2 + fib1 
  
    while fibM < n:  # 从斐波那契数列中找到*第一个*大于或等于数组长度（n）的数（fibM）
        fib2 = fib1 
        fib1 = fibM 
        fibM = fib2 + fib1 
  
    offset = -1
  
    while fibM > 1:  # 当fibM等于1，fib2等于0，后面没有元素了
        cur = min(offset+fib2, n-1)  # cur相当于二分查找中的mid
        
        if arr[cur] < target:  # target大于arr[cur]，转向cur的右边
            fibM = fib1        # 斐波那契下降一个单位
            fib1 = fib2 
            fib2 = fibM - fib1 
            offset = cur       # cur的右边需要把cur之前的部分加到fib2上
  
        elif arr[cur] > target:  # target小于arr[cur]，转向cur的左边
            fibM = fib2          # 斐波那契下降两个单位
            fib1 = fib1 - fib2 
            fib2 = fibM - fib1 
  
        else: 
            return cur
  
    if fib1 == 1 and arr[offset+1] == target: 
        # 如果仅余一个元素用于比较，检验fib1是否等于1，如果是，判断该元素是否为target
        return offset+1 
  
    # element not found. return -1  
    return -1
  
# Driver Code 
arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] 
n = len(arr) 
target = 10
print("Found at index:", fibMonaccianSearch(arr, target, n))