python查找算法举例

1. 线性查找算法

线性查找算法是一种简单的查找方法，它遍历整个数组，逐个比较元素，直到找到目标元素或遍历完整个数组。如果找到目标元素，返回其索引值，否则返回-1。

示例代码：

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

2. 二分查找算法

二分查找算法是一种高效的查找方法，它利用有序数组的特点，每次将查找范围缩小一半，直到找到目标元素或查找范围为空。如果找到目标元素，返回其索引值，否则返回-1。

示例代码：

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

3. 哈希查找算法

哈希查找算法是一种利用哈希表实现查找的方法，它将目标元素通过哈希函数映射到哈希表中的一个位置，如果该位置上存在目标元素，则返回其索引值，否则返回-1。

示例代码：

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])
    
    def search(self, key):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        return -1

4. 广度优先搜索算法

广度优先搜索算法是一种图遍历算法，它从指定节点开始遍历图，逐层扩展搜索范围，直到找到目标节点或遍历完整个图。如果找到目标节点，返回其路径，否则返回空。

示例代码：

from collections import deque

def bfs(graph, start, end):
    queue = deque()
    queue.append([start])
    visited = set()
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == end:
            return path
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            new_path = path + [neighbor]
            queue.append(new_path)
    return None