Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
2  
You can always rewrite a recursive function as a non-recursive one, using a stack. You rarely gain anything. –  Mariano Suárez-Alvarez Oct 7 '10 at 17:01
    
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. –  e.James Oct 7 '10 at 17:05
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. –  Aryabhata Oct 7 '10 at 17:10
    
@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. –  e.James Oct 7 '10 at 17:13
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 :) –  e.James Oct 7 '10 at 17:21
add comment

1 Answer 1

No longer relevant, keeping answer around for comments.

share|improve this answer
    
Sorry if I wasn't clear. I'm looking for the direct children of any given node, but without having an existing tree. I would like to use the function f to build the tree nodes, given only the index for each node and the total number of nodes. The index i is simply the position of the element. The values themselves are irrelevant, as long as they are properly sorted. –  e.James Oct 7 '10 at 17:10
    
@e.James, then it depends on the structure of the tree. What structure are you imposing on them? Can we assume N is a power of 2-1 and the tree is complete? –  Aryabhata Oct 7 '10 at 17:12
    
@Moron: No, I can not assume that N is a power of 2-1 (see my example, with N=8). If you want to get technical, the tree is a representation of all of the steps that would be taken in a standard binary search for every node. –  e.James Oct 7 '10 at 17:16
    
@e.James: I would suggest you not even mention binary tree! Why confuse matters? btw, by "standard" I presume you mean taking (high+low)/2 etc? Are we free to suggest a different binary search method? –  Aryabhata Oct 7 '10 at 17:23
    
@Moron: yes, that is what I meant by standard. I have no idea how I could ask this question without describing the binary tree. That's the only term I know of to describe this kind of structure! –  e.James Oct 7 '10 at 17:25
show 11 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.