数据结构顺序表查找

以下是数据结构顺序表查找的两种方法：

1. 顺序查找：从表的一端开始，依次将每个元素与给定值进行比较，直到找到该元素或查找完整个表。时间复杂度为O(n)。

   def sequential_search(lst, key):
       for i in range(len(lst)):
           if lst[i] == key:
               return i
       return -1 # 表示查找失败

2. 折半查找：前提是表中的元素必须有序排列。将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。时间复杂度为O(logn)。

   def binary_search(lst, key):
       low, high = 0, len(lst) - 1
       while low <= high:
           mid = (low + high) // 2
           if lst[mid] == key:
               return mid
           elif lst[mid] > key:
               high = mid - 1
           else:
               low = mid + 1
       return -1 # 表示查找失败