如何在严格递减数组中以最多2次查询找到目标值 复杂度O(sqrt(n))

核心采用**分块查找（跳步查找）**逻辑，适配严格递减数组特性调整比较规则即可满足要求，具体实现步骤如下：

• 第一步：确定分块步长
  取数组长度为n，步长s = ⌈√n⌉，将数组按s个元素为单位划分为多个连续块，最后不足s个元素的部分单独作为一块。
• 第二步：第一次查询定位目标所在块
  从数组起始位置开始，每隔s个元素查询一次取值：
  • 若当前查询值等于k，直接返回当前索引，总惩罚值仅为1；
  • 若当前查询值大于k，因数组严格递减，说明目标在当前位置右侧的区间，继续往后跳s个元素查询；
  • 若当前查询值小于k，说明目标在上一个块的区间范围内，停止跨块查询。
• 第三步：第二次查询命中目标
  在上一步锁定的块区间内依次查询元素，最多s次即可找到目标，结合跨块阶段的最多s次查询，总查询次数最坏为2√n，惩罚值最大为2，时间复杂度满足O(√n)要求。

示例验证 #

测试用例：数组[200, 150, 120, 115, 110, 100]，目标值k=110
数组长度n=6，取步长s=⌈√6⌉=3

1. 第一次查询索引为2的元素，取值为120，120>110，判定目标在索引2~5区间内，当前惩罚值p=1
2. 区间内查询索引4的元素，取值为110，命中目标，总惩罚值p=2，完全符合要求。
   内容的提问来源于stack exchange，提问作者zvonimir