Solution
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
int FindIndex(int *arr, int size, int num)
{
int index = 0;
while(index < size){
if(arr[index] == num){
return index;
}
index += abs(num - arr[index]);
}
return -1;
}
int main(int argc, char* argv[])
{
int arr[] = {4, 5, 6, 5, 6, 7, 8, 9, 10, 9, 10};
copy(begin(arr), end(arr), ostream_iterator<int>(cout, ","));
cout << endl;
for(int i = 0; i < 15; ++i){
cout << "Find " << setw(2) << left << i << " at ";
cout << FindIndex(arr, sizeof(arr) / sizeof(int), i);
cout << endl;
}
return 0;
}
Output
4,5,6,5,6,7,8,9,10,9,10,
Find 0 at -1
Find 1 at -1
Find 2 at -1
Find 3 at -1
Find 4 at 0
Find 5 at 1
Find 6 at 2
Find 7 at 5
Find 8 at 6
Find 9 at 7
Find 10 at 8
Find 11 at -1
Find 12 at -1
Find 13 at -1
Find 14 at -1
Press any key to continue . . .
Input : 10 (find first occurence of 10 without using linear search)
Output : 8
For example, consider the array :
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element)
Problem
Consider an array of integers wherein each element is +1 or -1 its preceding element. Given a number, find the first occurence of this number (index) in this array without using linear search.