Dada una array donde la diferencia entre elementos adyacentes es 1, escriba un algoritmo para buscar un elemento en la array y devuelva la posición del elemento (devuelva la primera aparición).
Ejemplos:
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
Un enfoque simple es recorrer la array dada uno por uno y comparar cada elemento con el elemento ‘x’ dado. Si coincide, devuelve index.
La solución anterior se puede optimizar utilizando el hecho de que la diferencia entre todos los elementos adyacentes es 1. La idea es comenzar a comparar desde el elemento más a la izquierda y encontrar la diferencia entre el elemento de array actual y x. Sea esta diferencia ‘diff’. A partir de la propiedad dada de array, siempre sabemos que x debe estar al menos a ‘diff’ de distancia, así que en lugar de buscar uno por uno, saltamos ‘diff’.
A continuación se muestra la implementación de la idea anterior.
C++
// 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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to search an element in an array where
// difference between all elements is 1
#include <stdio.h>
#include <stdlib.h>
// 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);
}
printf("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;
printf("Element %d is present at index ",
search(arr, n, 3));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
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#
// 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 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.
?>
Javascript
<script>
// Javascript 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
let 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);
}
document.write("number is not present!");
return -1;
}
// Driver program
let arr = [8 ,7, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3 ];
let n = arr.length;
let x = 3;
document.write( "Element " + x + " is present at index "
+ search(arr,n,3));
// This code is contributed by jana_sayantan.
</script>
Producción
Element 3 is present at index 7
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Buscar en una array donde los adyacentes difieren como máximo en k
Este artículo es una contribución de Rishabh . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA