1
$\begingroup$

Edit: question simplified to remove confusion

Assuming a sorted list of items with indexes from 1 to N, and given only an index number i and the maximum index N, is there a simple function which will return the two possible indexes that would be reached next in a binary search of the list?

Example:

i = 6 N = 8 LeftSearchIndex(i, N) = 5 RightSearchIndex(i, N) = 7 
  • 2
    You can always rewrite a recursive function as a non-recursive one, using a stack. You rarely gain anything.2010-10-07
  • 0
    True. I added the restriction on recursion to exclude the naive solution which simply produces the entire tree each time, and then selects the appropriate indexes. I can certainly go that route if need be, but I have a feeling that there should be a more elegant function.2010-10-07
  • 2
    @Mariano: Space is usually prime in Embedded devices. So even though theoretically iteration and recursion are equivalent, practically speaking, it makes a big difference.2010-10-07
  • 0
    @Moron: In my case, processing time is far more scarce than code space. That is why I want to remove the tree branch computation from the runtime.2010-10-07
  • 2
    @Moron: I've just realized that if you ever decide to change your username, these comments are going to make me look like a real jerk `:)`2010-10-07

1 Answers 1