• Post Reply 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 ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Exponential binary search

 
Greenhorn
Posts: 14
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm trying to apply the exponential binary search, but I'm facing problems regarding the power index. As you know, before I do the normal binary search, I need to keep comparing my key with the elements in my array until I find an element array[2^i] where key<array[2^i]. Then I call binary search with the boundaries 2^(i-1)...2^i. Now, my array contains 676 elements. Which means that starting from i=10, I'm out of the bounds of my array. So if key>array[2^1] and key>array[2^2]....till key>array[2^9], i will be incremented once more to become 10(i.e. 2^10=1024) and the comparison will be done again. But this time, since the array only has 676 elements, I will be out of bounds and I'll get an error. So say the element I'm looking for lies near the end of my array. Then, the first part of the algorithm would probably reach an i greater or equal 10 to find an element greater than my key. This will give me an ArrayOutOfBounds error. So what can one do to avoid this considering that one uses finite arrays? It seems like this is an obvious question to ask regarding the way this algorithm functions, but there doesn't seem to be that much information on it online. Thanks in advance.
 
Bartender
Posts: 689
17
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How about you check that the index you want to check is actually in the array before you check it? If you find that 2^i >= array.length then you set the upper boundary to array.length -1.

So your search boundary will either be

2^(i - 1) -> 2^i

Or it will be

2^(i - 1) -> array.length - 1.

Whichever boundaries you have, you perform a binary search on that section of the array and see if the item is in there.
 
Liar, liar, pants on fire! refreshing plug:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic