Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Algorithm-Please help guys!!!

Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Report post to moderator

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!!
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

30 seconds to difuse a loaf of bread ... here, use this tiny ad:
the value of filler advertising in 2021
    Bookmark Topic Watch Topic
  • New Topic