Efficient way to search an element
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 11but 9 first "occurs" at index -1
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 @Raphael Miedl and @Martin Zabel.
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 5array[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.