This week's book giveaway is in the General Computing forum.
We're giving away four copies of Emmy in the Key of Code and have Aimee Lucido on-line!
See this thread for details.
Win a copy of Emmy in the Key of Code this week in the General Computing forum!
    Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Paweł Baczyński
  • Piet Souris
  • Vijitha Kumara

Algorithm-Please help guys!!!

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Report post to moderator
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!!
 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
 
Destiny's powerful hand has made the bed of my future. And this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
    Bookmark Topic Watch Topic
  • New Topic
Boost this thread!