Efficient way to search an element
CArraysAlgorithmSortingSearchC Problem Overview
Recently I had an interview, where they asked me a "searching" question.
The question was:
> Assume there is an array of (positive) integers, of which each element is either +1 or -1 compared to its adjacent elements.
>
> Example:
>
> array = [4,5,6,5,4,3,2,3,4,5,6,7,8];
>
> Now search for 7 and return its position.
I gave this answer:
> Store the values in a temporary array, sort them, and then apply binary search.
>
> If the element is found, return its position in the temporary array.
(If the number is occurring twice then return its first occurrence)
But, they didn't seem to be satisfied with this answer.
What is the right answer?
C Solutions
Solution 1 - C
You can do a linear search with steps that are often greater than 1. The crucial observation is that if e.g. array[i] == 4 and 7 hasn't yet appeared then the next candidate for 7 is at index i+3. Use a while loop which repeatedly goes directly to the next viable candidate.
Here is an implementation, slightly generalized. It finds the first occurrence of k in the array (subject to the +=1 restriction) or -1 if it doesn't occur:
#include <stdio.h>
#include <stdlib.h>
int first_occurence(int k, int array[], int n);
int main(void){
int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
printf("7 first occurs at index %d\n",first_occurence(7,a,15));
printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
return 0;
}
int first_occurence(int k, int array[], int n){
int i = 0;
while(i < n){
if(array[i] == k) return i;
i += abs(k-array[i]);
}
return -1;
}
output:
7 first occurs at index 11
but 9 first "occurs" at index -1
Solution 2 - C
Your approach is too complicated. You don't need to examine every array element. The first value is 4, so 7 is at least 7-4 elements away, and you can skip those.
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
int len = sizeof array / sizeof array[0];
int i = 0;
int steps = 0;
while (i < len && array[i] != 7) {
i += abs(7 - array[i]);
steps++;
}
printf("Steps %d, index %d\n", steps, i);
return 0;
}
Program output:
Steps 4, index 11
Edit: improved after comments from @Martin Zabel.
Solution 3 - C
A variation of the conventional linear search could be a good way to go. Let us pick an element say array[i] = 2. Now, array[i + 1] will either be 1 or 3 (odd), array[i + 2] will be (positive integers only) 2 or 4 (even number).
On continuing like this, a pattern is observable - array[i + 2*n] will hold even numbers and so all these indices can be ignored.
Also, we can see that
array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7
so, index i + 5 should be checked next and a while loop can be used to determine the next index to check, depending on the value found at index i + 5.
While, this has complexity O(n) (linear time in terms of asymptotic complexity), it is better than a normal linear search in practical terms as all the indices are not visited.
Obviously, all this will be reversed if array[i] (our starting point) was odd.
Solution 4 - C
The approach presented by John Coleman is what the interviewer was hoping for, in all probability.
If you are willing to go quite a bit more complicated, you can increase expected skip length:
Call the target value k. Start with the first element's value v at position p and call the difference k-v dv with absolute value av. To speed negative searches, have a peek at the last element as the other value u at position o: if dv×du is negative, k is present (if any occurrence of k is acceptable, you may narrow down the index range here the way binary search does). If av+au is greater than the length of the array, k is absent. (If dv×du is zero, v or u equals k.)
Omitting index validity: Probe the ("next") position where the sequence might return to v with k in the middle: o = p + 2*av.
If dv×du is negative, find k (recursively?) from p+av to o-au;
if it is zero, u equals k at o.
If du equals dv and the value in the middle isn't k, or au exceeds av,
or you fail to find k from p+av to o-au,
let p=o; dv=du; av=au; and keep probing.
(For a full flash-back to '60ies texts, view with Courier. My "1st 2nd thought" was to use o = p + 2*av - 1, which precludes du equals dv.)
Solution 5 - C
STEP 1
Start with the first element and check if it's 7. Let's say c is the index of the current position. So, initially, c = 0.
STEP 2
If it is 7, you found the index. It's c. If you've reached the end of the array, break out.
STEP 3
If it's not, then 7 must be atleast |array[c]-7| positions away because you can only add a unit per index. Therefore, Add |array[c]-7| to your current index, c, and go to STEP 2 again to check.
In the worst case, when there are alternate 1 and -1s, the time complexity may reach O(n), but average cases would be delivered quickly.
Solution 6 - C
Here I am giving the implementation in java...
public static void main(String[] args)
{
int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8};
int pos=searchArray(arr,7);
if(pos==-1)
System.out.println("not found");
else
System.out.println("position="+pos);
}
public static int searchArray(int[] array,int value)
{
int i=0;
int strtValue=0;
int pos=-1;
while(i<array.length)
{
strtValue=array[i];
if(strtValue<value)
{
i+=value-strtValue;
}
else if (strtValue==value)
{
pos=i;
break;
}
else
{
i=i+(strtValue-value);
}
}
return pos;
}
Solution 7 - C
Here is a divide-and-conquer style solution. At the expense of (much) more bookkeeping, we can skip more elements; rather than scanning left-to-right, test in the middle and skip in both directions.
#include <stdio.h>
#include <math.h>
int could_contain(int k, int left, int right, int width);
int find(int k, int array[], int lower, int upper);
int main(void){
int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
printf("7 first occurs at index %d\n",find(7,a,0,14));
printf("but 9 first \"occurs\" at index %d\n",find(9,a,0,14));
return 0;
}
int could_contain(int k, int left, int right, int width){
return (width >= 0) &&
(left <= k && k <= right) ||
(right <= k && k <= left) ||
(abs(k - left) + abs(k - right) < width);
}
int find(int k, int array[], int lower, int upper){
//printf("%d\t%d\n", lower, upper);
if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1;
int mid = (upper + lower) / 2;
if(array[mid] == k) return mid;
lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid]));
if(lower >= 0 ) return lower;
upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper]));
if(upper >= 0 ) return upper;
return -1;
}
Solution 8 - C
const findMeAnElementsFunkyArray = (arr, ele, i) => {
const elementAtCurrentIndex = arr[i];
const differenceBetweenEleAndEleAtIndex = Math.abs(
ele - elementAtCurrentIndex
);
const hop = i + differenceBetweenEleAndEleAtIndex;
if (i >= arr.length) {
return;
}
if (arr[i] === ele) {
return i;
}
const result = findMeAnElementsFunkyArray(arr, ele, hop);
return result;
};
const array = [4,5,6,5,4,3,2,3,4,5,6,7,8];
const answer = findMeAnElementsFunkyArray(array, 7, 0);
console.log(answer);
Wanted to include a recursive solution to the problem. Enjoy