寻找被null包围的数组有效数据首尾索引的高效算法及命名

核心方法：变种二分查找 #

因为数组呈现「两侧为null、中间连续非null有效区间」的结构，最适合用二分查找的边界定位变种来分别定位第一个和最后一个有效元素，能把数组查询次数压缩到对数级别（对5000元素的数组，最多仅需约13次查询，远少于遍历的最坏5000次）。

定位第一个有效元素（左边界）的步骤：

• 初始化左指针 left = 0，右指针 right = 4999（数组最后一个元素索引）
• 循环执行直到 left > right：
  • 计算中间索引 mid = (left + right) // 2
  • 若 a[mid] 为 null，说明有效区间在mid右侧，将 left 更新为 mid + 1
  • 若 a[mid] 非 null，说明左边界在mid或左侧，将 right 更新为 mid - 1
• 循环结束后，left 即为第一个有效元素的索引

定位最后一个有效元素（右边界）的步骤：

• 初始化左指针 left = 0，右指针 right = 4999
• 循环执行直到 left > right：
  • 计算中间索引 mid = (left + right) // 2
  • 若 a[mid] 非 null，说明右边界在mid或右侧，将 left 更新为 mid + 1
  • 若 a[mid] 为 null，说明右边界在mid左侧，将 right 更新为 mid - 1
• 循环结束后，right 即为最后一个有效元素的索引

专业名称 #

这类操作属于边界二分查找（Binary Search for Boundaries），是标准二分查找的常见变种，专门用于在有序或具有明确分区特征的集合中定位连续区间的首尾边界。

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