9.python的几种二分查找实现

基础的二分查找

from typing import List


def binary_search(arr: List, target: int, left, right) -> int:
    """
    二分查找递归实现
    :param arr: 原数组
    :param target: 查询目标元素
    :param left: 左边界
    :param right: 右边界
    :return:
    """
    while left != right:
        mid = (left + right) // 2
        pivot = arr[mid]
        if target == pivot:
            return mid
        elif target > pivot:
            return binary_search(arr, target, mid + 1, right)
        else:
            return binary_search(arr, target, left, mid)

    return -1


def binary_search_without_recursion(arr: List, target: int) -> int:
    """
    二分查找的非递归版本
    :param arr:
    :param target:
    :return:
    """
    left = 0
    right = len(arr)

    while left < right:
        mid = left + (right - left) // 2
        pivot = arr[mid]
        if pivot == target:
            return mid
        elif pivot < target:
            # 大于 右边
            left = mid + 1
        else:
            # 小于 左边
            right = mid

    return -1


if __name__ == '__main__':
    arr = [1, 8, 10, 89, 1000, 1234]
    print(binary_search(arr, 8, 0, len(arr)))
    print(binary_search_without_recursion(arr, 8))

差值查找

核心公式mid = left + (right-left) * (target - arr[left]) / (arr[right] - arr[left])

from typing import List


def interpolation_search(arr: List, target: int, left, right) -> int:
    """
    \核心思想: 插值查找十分适合用于查找有序序列间隔差不多的序列，如间隔相同的等差序列，
    使用核心公式mid = left + (right-left) * (target - arr[left]) / (arr[right] - arr[left])
    计算出中值索引之后可有效的减少递归的次数，但在差值间隔较大的有序序列中递归的次数不一定比普通的二分查找少，
    其他的实现跟二分查找一样，只是在判断递归结束条件的使用，因为中值索引的计算引入了目标数据target，
    为防止target传入过大引起mid计算出来的结果超过原数组长度，需要增加额外的判断。

    差值查找适合 数据分布间隔相差差不多的情况!!
    :param arr:
    :param target:
    :return:
    """
    """因为target参与了mid的运算如果
    target是一个很大的数
    如1000000
    此时计算出来的mid的值远远大于arr.length - 1
    if (left > right | | target < arr[0] | | target > arr[arr.length - 1]) {
    return -1;
    }
    """
    if left > right or target < arr[left] or target > arr[right]:
        return -1
    while left <= right:
        # int((target - arr[left]) / (arr[right] - arr[left]))) 需要注意在python中 两个数相除模式返回float的类型
        mid = (left + (right - left) * int((target - arr[left]) / (arr[right] - arr[left])))
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1


if __name__ == '__main__':
    arr = [1, 8, 10, 89, 1000, 1234]
    print(interpolation_search(arr, 1234, 0, len(arr) - 1))

斐波那契黄金分割查找

斐波那契查找
1. 根据需求创建一个斐波那契数列
2. 根据原数组的长度找到最接近的一个斐波那契数列的长度
3. 如果原数组长度小于斐波那契数列要求的长度则由原数组最后一个元素填充
4. 根据斐波那契F(n) = F(n-1) + F(n-2) 拆分成F(n-1)左边 和 F(n-2)右边
   1. mid的计算公式 mid = low + F(k-1) -1 分割的左边界用于控制元素的范围 -1 是因为java数组从0开始 F(k-1) 则是F(n-1)即斐波那契切分出来左边的部分
   2. 如果目标值大于中值midVal 则说明需要从中值右边查找则是斐波那契分割的右边f(n-2)
   3. 如果目标值小于中值midVal 则说明需要从中值右边查找则是斐波那契分割的左边f(n-1)
   4. 递归查找结果分三种情况
      1. 没找到 分割到1个元素无法继续分割
      2. 找到了 mid的值落在正常原数组长度范围类直接返回
      3. 因为原数组不足斐波那契长度填充的情况，mid可能落在原数组长度之外，则直接返回原数组最后一个元素的索引即可

def create_fibonacci():
    arr = [0, 1]
    for i in range(10):
        arr.append(arr[-2] + arr[-1])
    return arr


def fibonacci_search(arr, target):
    """
    斐波那契查找
    1. 根据需求创建一个斐波那契数列
    2. 根据原数组的长度找到最接近的一个斐波那契数列的长度
    3. 如果原数组长度小于斐波那契数列要求的长度则由原数组最后一个元素填充
    4. 根据斐波那契F(n) = F(n-1) + F(n-2) 拆分成F(n-1)左边 和 F(n-2)右边
       1. mid的计算公式 mid = low + F(k-1) -1 分割的左边界用于控制元素的范围 -1 是因为java数组从0开始 F(k-1) 则是F(n-1)即斐波那契切分出来左边的部分
       2. 如果目标值大于中值midVal 则说明需要从中值右边查找则是斐波那契分割的右边f(n-2)
       3. 如果目标值小于中值midVal 则说明需要从中值右边查找则是斐波那契分割的左边f(n-1)
       4. 递归查找结果分三种情况
          1. 没找到 分割到1个元素无法继续分割
          2. 找到了 mid的值落在正常原数组长度范围类直接返回
          3. 因为原数组不足斐波那契长度填充的情况，mid可能落在原数组长度之外，则直接返回原数组最后一个元素的索引即可
    :param arr:
    :return:
    """
    length = len(arr)
    # 1. 根据需求创建一个斐波那契数列
    fibonacci = create_fibonacci()
    k = 0
    # 2. 根据原数组的长度找到最接近的一个斐波那契数列的长度
    for f in fibonacci:
        if f < length:
            k += 1
        else:
            break
    fibonacci_length = fibonacci[k]

    # 3.如果原数组长度小于斐波那契数列要求的长度则由原数组最后一个元素填充
    temp = arr
    if length < fibonacci_length:
        for i in range(fibonacci_length - length):
            temp.append(arr[-1])

    # 4.根据斐波那契F(n) = F(n-1) + F(n-2) 拆分成F(n-1)左边 和 F(n-2)右边
    left = 0
    right = len(arr)
    # 4. 递归查找结果分三种情况
    #  1. 没找到 分割到1个元素无法继续分割
    #  2.找到了 mid的值落在正常原数组长度范围类直接返回 因为如果长度不够斐波那契的分配需要追加一个一个元素
    #  3. 因为原数组不足斐波那契长度填充的情况，mid可能落在原数组长度之外，则直接返回原数组最后一个元素的索引即可
    while left < right:
        # 1. mid的计算公式 mid = low + F(k-1) -1 分割的左边界用于控制元素的范围 -1 是因为java数组从0开始 F(k-1) 则是F(n-1)即斐波那契切分出来左边的部分
        mid = left + fibonacci[k - 1] - 1
        if temp[mid] > target:
            # 3. 如果目标值小于中值midVal 则说明需要从中值右边查找则是斐波那契分割的左边f(n-1)
            right = mid + 1
            k -= 1
        elif temp[mid] < target:
            # 2. 如果目标值大于中值midVal 则说明需要从中值右边查找则是斐波那契分割的右边f(n-2)
            left = mid + 1
            k -= 2
        else:
            if mid > length - 1:
                #  2. 找到了 mid的值落在正常原数组长度范围类直接返回 因为如果长度不够斐波那契的分配需要追加一个一个元素
                return length - 1
            else:
                return mid


if __name__ == '__main__':
    # print(create_fibonacci())
    print(fibonacci_search([1, 8, 10, 89, 1000, 1234], 1234))