search an element in an array where adjacent numbers differ by +1 or -1
Sorry.. Rewriting to properly display.
I dont think you can use a binary search method, since the list obviously isn't sorted, so I suppose the best complexity you can hope for here is linear or O(n).
int FindElement(int *array, int length, int number, int occurrence)
{
if( array == NULL || length < occurrence )
{
return -1;
}
for( int i = 0; i < length ; i ++ )
{
if( array[i] == number )
occurrence --;
if( occurrence == 0 )
return i;
}
return -1; // Not found for the required number of occurrences.
}
In python
def FindElement(arr, num, occurent):
lenArray = len(arr)
index = []
for i in range(lenArray):
if arr[i] == num:
index.append(i)
occurent -= 1
break
i = i + 2
while(occurent > 0 and i < lenArray):
if arr[i] == num:
index.append(i)
i = i + 2
else:
i = i + 1
return index
>>> print(FindElement(l, 6,2))
[1,3]
Correction:
def FindElement(arr, num, occurent):
lenArray = len(arr)
index = []
for i in range(lenArray):
if arr[i] == num:
index.append(i)
occurent -= 1
break
i = i + 2
while(occurent > 0 and i < lenArray):
if arr[i] == num:
index.append(i)
i = i + 2
occurent -= 1
else:
i = i + 1
return index
This can be done in O(n/2) i.e O(n) time.
My Algo is as follows:
1) Lets say the 0th element is 'a'
2) 1st element can have 'a+1' or 'a-1'
3) 2nd element can have '(a+1)+1','(a+1)-1','(a-1)+1','(a-1)-1'. So 'a+2','a','a-2'
4) Likewise nth element can have 'a-n','a-n-2'..'a+n-2',a+n'.
5) Now lets say the element we want to search is 'x'. So the difference between 'x' and 'a' will be 'x-a'
6) As the difference is 'x-a', x should be in a position where it can fall under the series containing 'a+(x-a)'.
7) 'a+(x-a)' starts from 'x-a'th position.
8) Also note that elements will be even/odd alternatively based on the series above.
9) So we will do a linear search from 'x-a'th position and increment the index by 2.
int findElement(int[] arr,int x){
int n=arr.length;
int a=arr[0];
for (int i = Math.abs(x-a); i < n; i+=2) {
if(arr[i]==x)return i;
}
return -1;
}