CareerCup

boolean isArray(vector<int> A, int num) {
    int n=A.size();
    int pos=0,diff;
    while (pos<n) {
        diff=abs(num-A[pos]);
        if (diff==0) return true;
        pos+=diff;
    }
    return false;
}

boolean inArray(int[] A, int num) {
return A[0]<=num && num<=A[A.len-1];
}

ignore my previous solution, it is incorrect.

check min<=num && num<=max ? But it requires go through each element...
eg:
1,2,3,4,5,6
2,1,2,3,2,3
4,5,4,3,2,3

A better solution. The complexity of best case is O(1); worst case is O(n).

boolean isArray(int[] A, int num)
{
int len = A.len;
int m = len - 1 - abs( A[0] - A[len-1]);
if (A[0]<=num && num<=A[len-1])
return true;
else if (num>A[0]+m || num<A[0]-m)
return false;
else
// go through each element
}

The number is in array'A' if:
1. 0 <= num-a[0] < n when a[0] < a[n-1]...consecutive ascending numbers
2. 0 <= -(num-a[0]) < n when a[0] > a[n-1]...consecutive descending numbers

Seems related to One-dimensional random walk.
en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk

@Hendry can you please explain your solution

@Hendry your code fails for

int num=2;
int arr[]={3,2,1};

int find_index(int *a, int n, int x) {
int i = 0;
while(i < n && a[i] != x)
i += abs(a[i] - x);
return i < n ? i : -1;
}

@learner your code will fail for -4,-3,3,4 and element to be search is 3

ur input is incorrect:
-4, -3, ........, 3, 4:-> Every adjacent element should have distance of either +1 or -1
. On the contrary -3....3 has a distance of 6>
Run my also on this input:
-4, -3, -2, -1, 0, 1, 2 , 3 , 4

@learner
I think your code will fail for this example:
-3 -2 -1 0 -1 0 1 2 and the element to be searched is 2

@learner can you explain your thought process/algorithm

import java.util.Random;

public class FindInteger {

public static int findInteger(int k, int[] a, int start, int end) {

if (start < end) {
if (a[start] <= a[end]) {
// v is the numbers of decreases
int minus = (end - start - (a[end] - a[start])) / 2;
int plus = minus + (a[end] - a[start]);

if (k >= Math.max(a[start] - minus, a[end] - plus)) {
if (k <= Math.min(a[end] + minus, a[start] + plus)) {
// integer could validated
if (k == a[start])
return start;
else if (k == a[end])
return end;
else {
int t = findInteger(k, a, start, (start + end) / 2);
return t == -1 ? findInteger(k, a,
(start + end) / 2 + 1, end) : t;
}
} else {
return -1;
}
} else {
return -1;
}
} else {
int plus = (end - start - (a[start] - a[end])) / 2;
int minus = plus + (a[start] - a[end]);

if (k >= Math.max(a[end] - plus, a[start] - minus)) {
if (k <= Math.min(a[start] + plus, a[end] + minus)) {
if (k == a[start]) {
return start;
} else if (k == a[end]) {
return end;
} else {
int t = findInteger(k, a, start, (start + end) / 2);
return t == -1 ? findInteger(k, a,
(start + end) / 2 + 1, end) : t;
}
} else {
return -1;
}
} else {
return -1;
}
}
} else {
return a[start] == k ? start : -1;
}

}

public static void main(String[] args) {
Random random = new Random();

int k = 50;

int[] a = new int[10000];
a[0] = 5;
for (int i = 1; i < a.length; i++) {
int t = Math.abs(random.nextInt()) % 3;
if (t == 2) {
a[i] = a[i - 1] - 1;
} else {
a[i] = a[i - 1] + 1;
}
if (a[i] == k) {
System.out.println("Insert at #" + i);
}
}

int i = findInteger(k, a, 0, a.length - 1);
System.out.println("Found at #" + i);
}
}

@Spb: i don't understand how u deduce the same. Check my algo step by step below:
1. i = i + abs(-3 - 2); //i = 5
2. i = i + abs(0-2); // i = 7
3. a[7] = 2 //Find the element