Check out Manning's Countdown to 2014. Use discount code crdotd14 all month for 50% off every deal.
Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

Abay Kumar
Greenhorn

Joined: Sep 13, 2008
Posts: 1
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!!
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Please don't post the same question in multiple forums. It creates duplicate conversations and wastes the time of the people trying to help you.

Thanks,
Dave

It is sorta covered in the JavaRanch Style Guide.