题目

https://www.geeksforgeeks.org/searching-array-adjacent-differ-k/

证明

这个方法的关键在于利用了给定数组的一个特性：任意两个相邻元素之间的差值最大为 k。基于这个特性，我们可以对搜索过程进行优化。当我们在数组中查找一个特定的值 x 时，如果当前元素不是 x，那么我们可以根据当前元素与 x 的差值来估计跳过多少元素是安全的，而不必每次只移动一个位置。

解释和例子
假设我们的目标是查找值 x，当前位置的元素值为 arr[i]。根据题目条件，相邻元素之间的差值最多为 k。因此，如果 arr[i] 与 x 的差值是 d = |arr[i] - x|，我们可以推断，至少需要 d/k 步才能从 arr[i] 跳到 x（因为每步最多接近 x k 单位距离）。

举个例子，假设 k = 10，当前元素 arr[i] = 20，我们要找的 x = 40。那么 d = |20 - 40| = 20。由于每一步最多接近 x 10 单位距离，所以我们至少需要 20 / 10 = 2 步才可能到达一个值为 40 的元素。这意味着，下一次检查可以直接跳到 i + 2 的位置，而不是 i + 1。

代码

#include <iostream>
#include <cmath> // 用于std::abs

// 函数以数组arr、数组大小n、差值最大为k的步长和目标值x作为参数
int searchInArray(int arr[], int n, int k, int x) {
    int i = 0;
    while (i < n) {
        // 如果找到目标元素，返回其索引
        if (arr[i] == x) {
            return i;
        }

        // 计算跳跃的步长。由于相邻元素的差最多为k，我们可以跳过一定数量的元素
        // 跳跃步长基于当前元素与目标值之间的差值
        i += std::max(1, std::abs(arr[i] - x) / k);
    }

    // 如果没有找到，返回-1
    return -1;
}

// 主函数用于演示如何使用上述函数
int main() {
    int arr[] = {4, 5, 6, 7, 6}; // 示例数组
    int k = 1; // 相邻元素最大差值
    int x = 6; // 目标值
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组大小

    // 调用函数并打印结果
    std::cout << "Index of " << x << " is " << searchInArray(arr, n, k, x) << std::endl;

    return 0;
}