数据结构【查找】

**数据结构之查找**

在计算机科学中，查找是指从一个已知集合中找到满足某种条件的元素。查找算法是一类用于解决查找问题的算法，它们可以快速、有效地找到集合中的特定元素。

**1. 线性查找**

线性查找（Linear Search）是最简单的一种查找算法。它从集合中第一个元素开始，依次检查每个元素，直到找到满足条件的元素或遍历完整个集合。

def linear_search(arr, target):
 """
 线性查找算法 Parameters:
 arr (list): 待查找的数组 target: 目标值 Returns:
 int: 元素在数组中的索引，-1表示元素不存在 """
 for i in range(len(arr)):
 if arr[i] == target:
 return i # 找到目标值返回其索引 return -1 # 遍历完整个数组仍未找到目标值# 示例使用arr = [3,5,2,7,9]
target =7index = linear_search(arr, target)
print(f"元素 {target} 在数组中的索引是：{index}")

def binary_search(arr, target):
 """
 二分查找算法 Parameters:
 arr (list): 已经排序好的数组 target: 目标值 Returns:
 int: 元素在数组中的索引，-1表示元素不存在 """
 low =0 high = len(arr) -1 while low <= high:
 mid = (low + high) //2 if arr[mid] == target:
 return mid # 找到目标值返回其索引 elif arr[mid] < target:
 low = mid +1 else:
 high = mid -1 return -1 # 遍历完整个数组仍未找到目标值# 示例使用arr = [2,5,7,9,13]
target =7index = binary_search(arr, target)
print(f"元素 {target} 在数组中的索引是：{index}")

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

 def hash_function(self, key):
 return hash(key) % self.size def insert(self, key, value):
 index = self.hash_function(key)
 for i, (k, v) in enumerate(self.table[index]):
 if k == key:
 self.table[index][i] = (key, value)
 break else:
 self.table[index].append((key, value))

 def search(self, key):
 index = self.hash_function(key)
 for k, v in self.table[index]:
 if k == key:
 return v # 找到目标值返回其值 return None # 遍历完整个数组仍未找到目标值# 示例使用hash_table = HashTable(10)
hash_table.insert("apple",5)
hash_table.insert("banana",7)
print(hash_table.search("apple")) # 输出：5

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_end_of_word = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word):
 node = self.root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.is_end_of_word = True def search(self, word):
 node = self.root for char in word:
 if char not in node.children:
 return False # 找不到目标值返回False node = node.children[char]
 return node.is_end_of_word # 找到目标值返回True# 示例使用trie = Trie()
trie.insert("apple")
trie.insert("banana")
print(trie.search("apple")) # 输出：True