Python实现七大查找算法的示例代码
查找算法是计算机科学中的一个重要问题。本文将介绍Python现七大查找算法的示例代码,包括线性查找、二分查找插值查找、斐波那契查找、树表查找、哈希查找和跳跃表查找。
线性查找
线性查找一种简单的查找算法,适用于小型数据集。该算法从数据集的第一个元素开始,逐个比较每个元素,直到找到标元素或遍历完整个数据。
以下是Python实现线性查找的示例代码:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
述代码中,定义了一个linear_search函数,接受一个数组arr和目标元素target作为参数。在循环中,逐个比较数组中的元素,如果找到目标元素,则返回其索。如果遍历完整个数组仍未找到目标元素,则返回-1。
二分查找
二分查找是一种高效的查找算法,适用于有序数据集。该算法将集分成两个部分,每次比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直到找到目标素或无法继续分割。
以下是Python实现二分查找的示例代码:
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
上述代码中,定义了一个binary_search函数,接受一个有序arr和标元素target作为参数。在循环中,每次将数组分成两个部分,比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直找到目标元素或无法继续分割。如果遍历完整个数组仍未找到目标元素,则返回-1。
示例说明
以下是两个示例,说明如何使用linear_search和binary_search函数查找目标元素。
示例1
使用linear_search函数查找目标元素5。
arr = [1, 3, 5, 7, 9]
target = 5
result = linear_search(arr, target)
if result != -1:
print(f"目标元素target}在数组中的索引为{result}")
else:
print(f"目标元素{target}不在数组中")
输出结果```
目标元素5在数组中的索引为2
### 示例2
使用binary_search查找目标元素7。
```python
arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search(arr, target)
if result != -1:
print(f"目标元素{target}在数组中的索引为{result}")
else:
print(f目标元素{target}不在数组中")
输出结果:
目标元素7在数组中的索引为3
插值查找
插值查找是一种高效的查找算法,适用于有序数据集。该算法根据标元在数据集中的位置,估算其可能的位置,从而快速定位目标元素。
以下是Python实现插值查找示例代码:
def interpolation_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right and arr[left] <= target <= arr[right]:
pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
if arr[pos] == target:
return pos
elif arr[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
上述代码中,定义了一个interpolation_search函数接受一个有序数组arr和目标元素target作为参数。在循环中,根据目标元素在数据集中的位置,估算其可能的位置,从而快速定位目标元素。如果找到目标元素,则返回其索引。如果历完整个数组仍找到目标元素,则返回-1。
斐波那契查找
斐波那契查找是一种高效的查找算法,适用于有序数据集该算法利用斐波那契数列的特性,将数据集分成两个部分,每次比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直到找到目标元素或无法继续分割。
以下是Python实现斐波那契查找示例代码:
def fibonacci_search(arr, target):
fib1, fib2 = 0, 1
while fib2 < len(arr):
fib1, fib2 = fib2, fib1 + fib2
offset = -1
while fib2 > :
i = min(offset + fib1, len(arr) - 1)
if arr[i] < target:
fib2, fib1 = fib1, fib2 - fib1
offset = i
elif arr[i] > target:
fib2, fib1 = fib2 - fib1, fib1
else:
return i
if fib1 and arr[offset + 1] == target:
return offset + 1
return -1
上代码中,定义了一个fib_search函数,接受一个有序数组arr和目标元素target作为参数。在循环中,利用斐波那契数列的特性,将数据分成两个部分,每次比较中间元素,如果目标元素小于中间素,则在左半部分继续查找,否则在右半部分查找,直到找到目标元素或无法继续分割。如果找到目标元素,则返回其索引。如果遍历完整个数组仍未找到目标元素,则返回-1。
树表查找
树表查找是一种高效的查找算法,适用于有序数据集。算法将数据集构建成一棵二叉查找树,每次比较中间节点,如果标元素小于中间节点,则在左子树继续查找,否则在右子树查找,直到找到目标元素或无继续分割。
以下是Python现树表查找的示例代码:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(arr):
if not arr:
return None
mid = len(arr) // 2
root = TreeNode(arr[mid])
root.left = build_tree(arr[:mid])
root.right = build_tree(arr[mid+1:])
return root
def tree_search(root, target):
if not root:
return -1
if root.val == target:
return 0
elif root.val < target:
result = tree_search(root.right, target)
if result == -1:
return -1
else:
return result + 1
else:
result = tree_search(root.left, target)
if result == -1:
return -1
else:
return result + 1
上述代码中,定义了一个TreeNode类表示二叉查找树的节点,包括节点值和左右子树。build_tree函数接受一个有序数组arr为参数,构建一棵二叉查找树。tree_search函数接受一个二叉找树的根节点root和目标元素target作为参数,递归比较中间节点,如果目标元素小于中间节点,则在左子树继续查找,否则在右子树查找,直到找到目标元素或法继续分割。如果找到目标元素,则返回其深度。如果遍历完整个树仍未找到目标元素,则返回-1。
哈希查找
哈希查找是一种效的查找算法,适用于大型数据集。该算法将数据集映射到哈希表中,每次查找时,根据目标元素的哈希值,快速定位其可能的位置,从而快速定位目标元素。
以下是Python实现哈希查找的示例代码:
class HashTable:
def __init__(self):
self.size = 10
self.table = [[] for _ in range(self.size)]
def hash_func(self, key):
return key % self.size
def insert(self, key, value):
hash_key = self.hash_func(key)
for i, item in enumerate(self.table[hash_key]):
if item[0] == key:
self.table[hash_key][i] = (key, value)
return
self.table[hash_key].append((key, value))
def search(self, key):
hash_key = self.hash_func(key)
for item in self.table[hash_key]:
if item[0] == key:
return item[1]
return None
上述代码中,定义了一个HashTable类表示哈希表,包括哈希表大小和哈希表数组。hash_func函数接受一个键值key作为参数,返回其哈希值。insert函数接受一个键值key和值value作为参数,将其插入哈希表中。search函数接受一个键值key作参数,根据其哈希值快速定位其可能的位置,从而快速定位目标元素。如果找到目标元,则返回值。如果遍历完整个哈希表仍未找到目标元素,则返回None。
跳跃表查找
跳跃表查找是一种高效的查找算法,适用于大型数据集。算法将数据集构建成一种特殊的链表,每个节点包含多个指针,可以快速跳过一些节点,从而快速定位目标元素。
以下是Python实现跳跃表查找的示例代码:
import random
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.down = None
class SkipList:
def __init__(self):
self.head = Node(-1)
self.levels = 1
def insert(self, val):
level = 1
while random.random() < 0.5:
level += 1
if level > self.levels:
self.head.next = Node(val)
for i in range(self.levels, level):
node = Node(-1)
node.down = self.head.next
self.head.next = node
self.levels = level
node = self.head.next
prev = self.head
for i in range(self.levels - 1, -1, -1):
while node and node.val < val:
prev, node = node, node.next
if i < level:
new_node = Node(val)
new_node.next = node
prev.next = new_node
new_node.down = down_node
down_node = new_node
prev, node = prev.down, node.down
def search(self, val):
node = self.head.next
for i in range(self.levels - 1, -1, -1):
while node and node.val < val:
node = node.next
if node and node.val == val:
return True
node = node.down
return False
上述代码中,定义了一个Node类表示跳跃表的节点,包括节点值、下一个节点和下一层节点。SkipList类表示跳跃表包括头节点和层数。insert函数接受一个值val作为参数,将其插入跳跃表中。search函数接受一个值val作为参数,快速定位目标元素。如果找到目元素,则返回True。如果遍历完整个跳跃表仍未找到目标元素,则False。
总结
本文介绍了Python实现七大查找算法的示例代码,包括线性查找、二分查找、值查找、斐波那契查找、树表查找、哈希查找和跳跃表查找不同的查找算法适用于不同的数据集和场景,需要根据实际情况选择合适的算法。在实际应中,需要注意算法的时间复杂度和空间复杂度,以获得更好的性能。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python实现七大查找算法的示例代码 - Python技术站