QUESTION
Given an array of n integers. Each array element is obtained by adding either +1 or -1 to previous element i.e absolute difference between any two consecutive elements is 1.\n\nThe task is to search an element index with the minimum number of comparison (less than simple element by element search). If the element is present multiple time, then print the smallest index. \n\nIf the element is not present print -1\n.
“TESTCASE_1”: “8\n5 4 5 6 5 4 3 2\n4\n###—###SEPERATOR—###—\n1”, “TESTCASE_2”: “8\n5 4 5 6 4 3 2 3\n9\n###—###SEPERATOR—###—\n-1”, “TESTCASE_3”: “7\n1 4 2 3 4 3 2\n3\n###—###SEPERATOR—###—\n3”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
#include<bits/stdc++.h>
using namespace std;
int search(int arr[], int n, int x)
{
// Searching x in arr[0..n-1]
int i = 0;
while (i <= n-1)
{
// Checking if element is found.
if (arr[i] == x)
return i;
// Else jumping to abs(arr[i]-x).
i += abs(arr[i]-x);
}
return -1;
}
// Driven Program
int main()
{
int a[8],x,sizeofarray;
cin >> sizeofarray;
for (int i = 0; i < sizeofarray; ++i)
{
cin >> a[i];
}
int n = sizeof(a)/sizeof(a[0]);
cin>>x;
cout << search(a, n, x) << endl;
return 0;
}