Searching for an element in array of adjacent numbers | Letuscode
Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?
For example consider the array
Read full article from Searching for an element in array of adjacent numbers | Letuscode
Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?
For example consider the array
{1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5.
Let us assume we are searching for a number x+3 in an array.
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have
x, x+1, x+2, x+3, ...
x, x+1, x, x+1, ...
x, x-1, x, x+1, ...
x, x-1, x-2, x-1, ...
x, x+1, x+2, x+1, ...
etc...
We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.
The time complexity of the above procedure is still
O(n), because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).
Example, search for number 6 in the array
{4, 5, 4, 5, 4, 5, 4, 5, 4, 5}, we have to make 5 jumps to conclude that 6 is not present.
bool search_adj(const vector<int> &arr, int s) {
bool ret = false;
size_t i;
for( i = 0; i < arr.size(); ) {
if( arr[i] == s ) {
ret = true;
break;
}
else {
i += abs(s-arr[i]);
}
}
return ret;
}
Read full article from Searching for an element in array of adjacent numbers | Letuscode
