posted 14 years ago
Hi,
I have a problem at hand and i kinda need some help.
I have an array with some values inside and basically i need to check if the array (index value+1) == the actual value in that index and if so, i need to increase a counter.
int a[] = {-1, 0, 2, 4, 5, 6, 7}
and the result shud be 4 for this because ther are 4 elements in this array which satisfy the condition... as, starting from index a[3] till a[6]....the value of index is equal to (index+1)
like a[3] = 4
a[4] = 5
a[5] = 6
a[6] = 7
but the catch is to do it in O(log N)...and not o(n).....
we cud assume tat the array is always sorted in ascending order.
A friend's algo so far
)If the middle value is greater than its index (not the array size), we know that none of the entries above it (which are also greater) will work. Next i shud check the middle value of the lower half of the array.
2)If the middle value is less than its index, we know none of the entries below it will work either. So in that case i shud check the middle value of the upper half of the array.
3)If the middle value = its index, then you can't say anything about either the upper or lower half. I will have to check both.
But i am having a trouble here, how am i supposed to half the arrays when you are given one whole array? if i copy one half of the array elements into another temporary array the log N complexity will b lost as i will have to traverse thro each element of the half...
i am unable to proceed becoz the above is an idea of binary searchin and binary searching depends on the fact that the array size is halved every time....somebdy please help!!
thnx a million!!