python查找算法

Python中常用的查找算法有线性查找、二分查找和哈希查找。

1. 线性查找：逐个遍历列表或数组，直到找到目标元素或遍历完所有元素。时间复杂度为O(n)。
示例代码：

   def linear_search(arr, target):
       for i in range(len(arr)):
           if arr[i] == target:
               return i
       return -1  # 目标元素不存在
   
   # 使用示例
   array = [4, 2, 1, 5, 3]
   target = 5
   index = linear_search(array, target)
   print(f"目标元素 {target} 的索引为: {index}")

2. 二分查找：对于已经排序的列表或数组，通过比较中间元素与目标元素的大小关系，缩小查找范围。时间复杂度为O(log n)。
示例代码：

   def binary_search(arr, target):
       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  # 目标元素不存在
   
   # 使用示例
   array = [1, 2, 3, 4, 5]
   target = 3
   index = binary_search(array, target)
   print(f"目标元素 {target} 的索引为: {index}")

3. 哈希查找：利用哈希函数将元素映射到哈希表的特定位置，通过查询哈希表找到目标元素。时间复杂度为O(1)（在理想情况下）。
示例代码：

   def hash_search(hash_table, target):
       if target in hash_table:
           return hash_table[target]
       else:
           return -1  # 目标元素不存在
   
   # 使用示例
   hash_table = {"apple": 1, "banana": 2, "orange": 3}
   target = "banana"
   value = hash_search(hash_table, target)
   print(f"目标元素 {target} 的值为: {value}")

以上是Python中常用的查找算法，可以根据具体需求选择合适的算法。