Search in an array where adjacent elements differ by at most k

Easy

Problem

Adjacent elements of the array differ by at most k. Return the first index of x, doing better than checking every element in turn.

Example 1

Input:  arr = [4, 5, 6, 7, 6], k = 1, x = 6
Output: 2

Also asked as: Searching in an array where adjacent differ by at most k

Test cases

Case 1

Input:    [4,5,6,7,6], 1, 6
Expected: 2

Case 2

Input:    [20,40,50,70,70,60], 20, 60
Expected: 5

Case 3

Input:    [5], 3, 5
Expected: 0

Case 4

Input:    [1,2,3], 1, 9
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Jump by the guaranteed gap

Time O(n / k) roughlySpace O(1)

Since neighbours differ by ≤ k, the target is at least |a[i] − target| / k positions away — skip that many.

function search(a, k, target) {
let i = 0;
while (i < a.length) {
if (a[i] === target) return i;
i += Math.max(1, Math.floor(Math.abs(a[i] - target) / k));
}
return -1;
}