Efficient way to search an element

by

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

Leave a Comment