Search in an array where adjacent elements differ by at most k
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
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;}