# 在相鄰項最多相差 k 的數組中搜索 > 原文： [https://www.geeksforgeeks.org/searching-array-adjacent-differ-k/](https://www.geeksforgeeks.org/searching-array-adjacent-differ-k/) 步長數組是一個整數數組，其中每個元素與其相鄰元素的差異最多為 k。 給定鍵 x，如果存在多個元素，則需要找到 x 的索引值，并返回鍵的首次出現。 例子： ``` Input : arr[] = {4, 5, 6, 7, 6} k = 1 x = 6 Output : 2 The first index of 6 is 2. Input : arr[] = {20, 40, 50, 70, 70, 60} k = 20 x = 60 Output : 5 The index of 60 is 5 ``` 此問題主要是[的擴展，在相鄰元素之間的差為 1](https://www.geeksforgeeks.org/search-an-element-in-an-array-where-difference-between-adjacent-elements-is-1/) 的數組中搜索元素。 **簡單方法**可以一次遍歷給定數組，并將每個元素與給定元素“ x”進行比較。 如果匹配，則返回索引。 利用所有相鄰元素之間的差異最多為 k 的事實，可以對**優化上述解決方案。 這個想法是從最左邊的元素開始比較，并找出當前數組元素和 x 之間的差異。 將此差異設為“ diff”。 從 array 的給定屬性中，我們始終知道 x 必須至少相距'diff / k'，因此，我們不逐一搜索，而是跳了'diff / k'。** 以下是上述想法的實現。 ## C++ ```cpp // C++ program to search an element in an array? // where difference between all elements is 1 #include<bits/stdc++.h> using namespace std; // x is the element to be searched in arr[0..n-1] // such that all elements differ by at-most k. int search(int arr[], int n, int x, int k) { ????// Traverse the given array starting from ????// leftmost element ????int i = 0; ????while (i < n) ????{ ????????// If x is found at index i ????????if (arr[i] == x) ????????????return i; ????????// Jump the difference between current ????????// array element and x divided by k ????????// We use max here to make sure that i ????????// moves at-least one step ahead. ????????i = i + max(1, abs(arr[i]-x)/k); ????} ????cout << "number is not present!"; ????return -1; } // Driver program to test above function int main() { ????int arr[] = {2, 4, 5, 7, 7, 6}; ????int x = 6; ????int k = 2; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Element " << x? << " is present at index " ?????????<< search(arr, n, x, k); ????return 0; } ``` ## Java ```java // Java program to search an element in? // an array where difference between all // elements is 1 import java.io.*; class GFG { ????// x is the element to be searched? ????// in arr[0..n-1] such that all? ????// elements differ by at-most k. ????static int search(int arr[], int n,? ????????????????????????????int x, int k) ????{ ????????// Traverse the given array starting ????????// from leftmost element ????????int i = 0; ????????while (i < n) { ????????????// If x is found at index i ????????????if (arr[i] == x) ????????????????return i; ????????????// Jump the difference between? ????????????// current array element and x ????????????// divided by k We use max here ????????????// to make sure that i moves? ????????????// at-least one step ahead. ????????????i = i + Math.max(1, Math.abs(arr[i]? ??????????????????????????????????????- x) / k); ????????} ????????System.out.println("number is " +? ????????????????????????????????"not present!"); ????????return -1; ????} ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int arr[] = { 2, 4, 5, 7, 7, 6 }; ????????int x = 6; ????????int k = 2; ????????int n = arr.length; ????????System.out.println("Element " + x + ????????????????????????" is present at index " ????????????????????????+ search(arr, n, x, k)); ????} } // This code is contributed by vt_m ``` ## Python3 ```py # Python 3 program to search an element in an array? # where difference between all elements is 1 # x is the element to be searched in arr[0..n-1] # such that all elements differ by at-most k. def search(arr, n, x, k): ????# Traverse the given array starting from ????# leftmost element ????i = 0 ????while (i < n): ????????# If x is found at index i ????????if (arr[i] == x): ????????????return i ????????# Jump the difference between current ????????# array element and x divided by k ????????# We use max here to make sure that i ????????# moves at-least one step ahead. ????????i = i + max(1, int(abs(arr[i] - x) / k)) ????print("number is not present!") ????return -1 # Driver program to test above function arr = [2, 4, 5, 7, 7, 6] x = 6 k = 2 n = len(arr) print("Element", x, "is present at index",search(arr, n, x, k)) # This code is contributed # by Smitha Dinesh Semwal ``` ## C# ```cs // C# program to search an element in? // an array where difference between? // all elements is 1 using System; class GFG { ????// x is the element to be searched? ????// in arr[0..n-1] such that all? ????// elements differ by at-most k. ????static int search(int []arr, int n,? ??????????????????????????int x, int k) ????{ ????????// Traverse the given array starting ????????// from leftmost element ????????int i = 0; ????????while (i < n)? ????????{ ????????????// If x is found at index i ????????????if (arr[i] == x) ????????????????return i; ????????????// Jump the difference between? ????????????// current array element and x ????????????// divided by k We use max here ????????????// to make sure that i moves? ????????????// at-least one step ahead. ????????????i = i + Math.Max(1, Math.Abs(arr[i]? ????????????????????????????????????- x) / k); ????????} ????????Console.Write("number is " +? ??????????????????????"not present!"); ????????return -1; ????} ????// Driver Code ????public static void Main() ????{ ????????int []arr = { 2, 4, 5, 7, 7, 6 }; ????????int x = 6; ????????int k = 2; ????????int n = arr.Length; ????????Console.Write("Element " + x +? ??????????????????????" is present at index " +? ????????????????????????search(arr, n, x, k)); ????} } // This code is contributed by Nitin Mittal. ``` ## PHP ```php <?php // PHP program to search an // element in an array where // difference between all? // elements is 1 // x is the element to be? // searched in arr[0..n-1] // such that all elements? // differ by at-most k. function search($arr, $n, $x, $k) { ????// Traverse the given array ????// starting from leftmost element ????$i = 0; ????while ($i < $n) ????{ ????????// If x is found at index i ????????if ($arr[$i] == $x) ????????????return $i; ????????// Jump the difference between current ????????// array element and x divided by k ????????// We use max here to make sure that i ????????// moves at-least one step ahead. ????????$i = $i + max(1, abs($arr[$i] - $x) / $k); ????} ????echo "number is not present!"; ????return -1; } // Driver Code { ????$arr = array(2, 4, 5, 7, 7, 6); ????$x = 6; ????$k = 2; ????$n = sizeof($arr)/sizeof($arr[0]); ????echo "Element $x is present".? ?????????????????????"at index ", ????????search($arr, $n, $x, $k); ????return 0; } // This code is contributed by nitin mittal. ?> ``` **輸出**： ``` Element 6 is present at index 5 ``` * * * * * *