|
A step array is an array of integers where each element has a difference of at most k with its neighbor. Given a key x, we need to find the index value of x if multiple-element exist to return the first occurrence of the key.
Examples:
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
This problem is mainly an extension of Search an element in an array where difference between adjacent elements is 1.
A Simple Approach is to traverse the given array one by one and compare every element with the given element ‘x’. If matches, then return index.
The above solution can be Optimized using the fact that the difference between all adjacent elements is at most k. The idea is to start comparing from the leftmost element and find the difference between the current array element and x. Let this difference be ‘diff’. From the given property of the array, we always know that x must be at least ‘diff/k’ away, so instead of searching one by one, we jump ‘diff/k’.
Below is the implementation of the above idea.
C++
<?php
function search($arr, $n, $x, $k)
{
$i = 0;
while ($i < $n)
{
if ($arr[$i] == $x)
return $i;
$i = $i + max(1, abs($arr[$i] - $x) / $k);
}
echo "number is not present!";
return -1;
}
{
$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;
}
?>
|
Javascript
<script>
function search(arr, n, x, k)
{
var i = 0;
while (i < n)
{
if (arr[i] == x)
return i;
i = i + Math.max(1, Math.abs(arr[i]-x)/k);
}
document.write( "number is not present!");
return -1;
}
var arr = [2, 4, 5, 7, 7, 6];
var x = 6;
var k = 2;
var n = arr.length;
document.write( "Element " + x + " is present at index "
+ search(arr, n, x, k));
</script>
|
Output:
Element 6 is present at index 5
Time Complexity: O(n)
Auxiliary Space: O(1)
|
