有序整数序列中元素高效查找的最优数据组织方法

你之前用普通列表的in关键字判断元素存在，时间复杂度是O(n)，数据量较大时效率偏低。针对有序整数序列的场景，有两种更高效的实现方式：

1. 二分查找（保留有序结构，时间复杂度O(log n)） #

因为序列本身有序，二分查找是最优选择，Python标准库的bisect模块已经封装了相关实现，无需手写二分逻辑：

import bisect

def is_in_sorted_sequence(element, sorted_seq):
    idx = bisect.bisect_left(sorted_seq, element)
    # 检查索引是否在序列范围内，且对应位置元素等于目标值
    if idx < len(sorted_seq) and sorted_seq[idx] == element:
        print('yes')
    else:
        print('no')

# 测试示例
is_in_sorted_sequence(2, [1,2,3])
is_in_sorted_sequence(4, [1,2,3])

bisect_left会返回目标元素应该插入的位置，通过判断该位置的元素是否等于目标，就能确定元素是否存在。这种方法完全保留了序列的有序性，同时查找效率远高于普通列表的in操作。

2. 转换为集合（无需保留有序结构，时间复杂度O(1)） #

如果你的场景不需要维持序列的有序性，只是单纯需要快速判断元素是否存在，可以把有序序列转换为集合。集合的成员判断操作基于哈希实现，时间复杂度为O(1)：

def is_in_set(element, sorted_seq):
    element_set = set(sorted_seq)
    print('yes' if element in element_set else 'no')

# 测试示例
is_in_set(2, [1,2,3])
is_in_set(4, [1,2,3])

注意：集合会自动去重，如果原序列有重复元素，转换为集合后不影响存在性判断，但会丢失重复信息。如果需要保留原有序列的重复元素或有序性，这种方法不适用。

补充：使用array模块优化内存（不改变查找效率） #

如果序列元素都是整数，用array.array替代普通列表可以节省内存空间（存储二进制整数而非对象引用），但查找效率和普通列表一致，需要配合二分查找才能实现高效判断：

import bisect
import array

# 创建整数数组
sorted_arr = array.array('i', [1,2,3])

def is_in_sorted_array(element, sorted_arr):
    idx = bisect.bisect_left(sorted_arr, element)
    if idx < len(sorted_arr) and sorted_arr[idx] == element:
        print('yes')
    else:
        print('no')

is_in_sorted_array(2, sorted_arr)

内容的提问来源于stack exchange，提问作者3sm1r