在相邻元素之间的差为 1 的数组中搜索元素 · GeeksForGeeks 中文系列教程

# 在相邻元素之间的差为 1 的数组中搜索元素 > 原文： [https://www.geeksforgeeks.org/search-an-element-in-an-array-where-difference-between-adjacent-elements-is-1/](https://www.geeksforgeeks.org/search-an-element-in-an-array-where-difference-between-adjacent-elements-is-1/) 给定一个数组，其中相邻元素之间的差为 1，编写一种算法来搜索数组中的元素并返回该元素的位置（返回第一个出现的元素）。 **示例**： ``` Let element to be searched be x Input: arr[] = {8, 7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3} x = 3 Output: Element 3 found at index 7 Input: arr[] = {1, 2, 3, 4, 5, 4} x = 5 Output: Element 5 found at index 4 ``` **简单方法**可以一次遍历给定数组，并将每个元素与给定元素“ x”进行比较。如果匹配，则返回索引。可以使用所有相邻元素之间的差异为 1 的事实对上述解决方案进行**优化。[想法]是从最左侧的元素开始进行比较，然后找出当前数组元素与 x 之间的差异。将此差异设为“ diff”。从 array 的给定属性中，我们始终知道 x 必须至少相距'diff'，因此，我们不逐一搜索，而是跳了'diff'。** 感谢 RajnishKrJha 建议此解决方案。以下是上述想法的实现。 ## 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] int search(int arr[], int n, int x) { // 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 i = i + abs(arr[i]-x); } cout << "number is not present!"; return -1; } // Driver program to test above function int main() { int arr[] = {8 ,7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3 }; int n = sizeof(arr)/sizeof(arr[0]); int x = 3; cout << "Element " << x << " is present at index " << search(arr,n,3); 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] static int search(int arr[], int n, int x) { // 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 i = i + Math.abs(arr[i]-x); } System.out.println ("number is not" + " present!"); return -1; } // Driver program to test above function public static void main (String[] args) { int arr[] = {8 ,7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3 }; int n = arr.length; int x = 3; System.out.println("Element " + x + " is present at index " + search(arr,n,3)); } } //This code is contributed by vt_m. ``` ## Python 3 ``` # 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] def search(arr, n, x): # 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 i = i + abs(arr[i] - x) print("number is not present!") return -1 # Driver program to test above function arr = [8 ,7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3 ] n = len(arr) x = 3 print("Element" , x , " is present at index ", search(arr,n,3)) # This code is contributed by Smitha ``` ## C# ```cs // C# program to search an element // in an array where difference // between all elements is 1 using System; public class GFG { // in arr[0..n-1] static int search(int []arr, int n, int x) { // 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 i = i + Math.Abs(arr[i] - x); } Console.WriteLine ("number is not" + " present!"); return -1; } // Driver code public static void Main() { int []arr = {8 ,7, 6, 7, 6, 5, 4,3, 2, 3, 4, 3 }; int n = arr.Length; int x = 3; Console.WriteLine("Element " + x + " is present at index " + search(arr, n, 3)); } } // This code is contributed by Sam007 ``` ## 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] function search($arr, $n, $x) { // 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 $i = $i + abs($arr[$i] - $x); } echo "number is not present!"; return -1; } // Driver Code $arr = array(8 ,7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3); $n = sizeof($arr); $x = 3; echo "Element " , $x , " is present " , "at index ", search($arr, $n, 3); // This code is contributed // by nitin mittal. ?> ``` **输出**： ``` Element 3 is present at index 7 ``` [**在相邻相差最多 k 的数组中搜索**](https://www.geeksforgeeks.org/searching-array-adjacent-differ-k/)