Efficient way to search an element

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.

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.)

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

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.