选择数据结构时要考虑读取、插入、删除和查找操作的频率。

  • 数组：按下标读取快，中间插入较慢。
  • 栈：后进先出，可用于括号匹配和函数调用。
  • 队列：先进先出，可用于任务调度。
  • 哈希表：平均查找速度快，适合键值映射。
  • 树：适合表示层级关系和有序数据。
PYTHON
def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1

二分查找要求数据已经排序，时间复杂度为 O(log n)。