博客

Python 语言实现六大查找算法

  • Post category:Python

下面是关于“Python语言实现六大查找算法”的完整攻略。

1. 六大查找算法

六大查找算法是指顺序查找、二分查找、插值查找、斐波那契查找、树表查找和哈希查找这六种常用的查找算法。这些算法是计算机科学中最基本的算法之一，也是Python开发者必须掌握的算法之一。

2. 算法实现

下面是使用Python实现六大查找算法的完整代码。

2.1 顺序查找

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

2.2 二分查找

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

2.3 插值查找

def interpolation_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high and x >= arr[low] and x <= arr[high]:
        pos = low + int(((float(high - low) / (arr[high] - arr[low])) * (x - arr[low])))
        if arr[pos] == x:
            return pos
        if arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    return -1

2.4 斐波那契查找

def fibonacci_search(arr, x):
    fib2, fib1 = 0, 1
    while fib1 < len(arr):
        fib2, fib1 = fib1, fib2 + fib1
    offset = -1
    while fib1 > 1:
        i = min(offset + fib2, len(arr) - 1)
        if arr[i] < x:
            fib1, fib2 = fib2, fib1 - fib2
            offset = i
        elif arr[i] > x:
            fib1, fib2 = fib1 - fib2, fib2
        else:
            return i
    if fib1 == 1 and arr[offset + 1] == x:
        return offset + 1
    return -1

2.5 树表查找

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val

def tree_search(root, x):
    if not root:
        return None
    if root.val == x:
        return root
    elif root.val > x:
        return tree_search(root.left, x)
    else:
        return tree_search(root.right, x)

2.6 哈希查找

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def hash_func(self, x):
        return x % self.size

    def insert(self, x):
        hash_val = self.hash_func(x)
        self.table[hash_val].append(x)

    def search(self, x):
        hash_val = self.hash_func(x)
        if x in self.table[hash_val]:
            return True
        else:
            return False

3. 示例

下面是两个查找算法的示例，分别展示了二分查找和哈希查找的实现。

3.1 二分查找示例

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

输出：

Element is present at index 3

3.2 哈希查找示例

hash_table = HashTable()
hash_table.insert(5)
hash_table.insert(10)
hash_table.insert(15)
print(hash_table.search(10))
print(hash_table.search(20))

输出：

True
False

4. 总结

六大查找算法是计算机科学中最基的算法之一，也是开发者必须掌握的算法之一。在Python中，我们可以使用各种数据结构和算法来实现这些基本算法。在实际应用中，我们可以根据具体问题选择适当的算法来进行开发和实现。

Tags: ,