Searching and Sorting: Search an array where adjacent differ by at most k

Problem Statement:

You are given an array and has a difference of atmost k.

Given a key ‘x’, we need to find the index value of ‘x’.

Example

Input : {1, 2, 3, 4, 3}
k = 1
x = 3

Output : 2
First index of 3 is 2.

Solution

The solution is very simple, we need to use modified binary search method.

We start by comparing the left most element and then we find the difference between the current element and the ‘x’.

We know that ‘x’ must be at-least “diff/k” away, hence we jump “diff/k” times.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
int search(int arr[], int n, int x, int k)
{

    int i = 0;
    while (i < n)
    {
        if (arr[i] == x)
            return i;

        i = i + max(1, abs(arr[i]-x)/k);
    }
  
    cout << "Number is not present";
    return -1;
}
  
int main()
{
    int arr[] = {2, 4, 5, 7};
    int x = 2;
    int k = 2;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Key " << x  << " is present at index " << search(arr, n, x, k)<<endl;
    return 0;
}

Output:

Key 2 is present at index 0