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?


i = 6
N = 8
LeftSearchIndex(i, N) = 5
RightSearchIndex(i, N) = 7
  • 2
    $\begingroup$ You can always rewrite a recursive function as a non-recursive one, using a stack. You rarely gain anything. $\endgroup$ – Mariano Suárez-Álvarez Oct 7 '10 at 17:01
  • $\begingroup$ 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. $\endgroup$ – e.James Oct 7 '10 at 17:05
  • 2
    $\begingroup$ @Mariano: Space is usually prime in Embedded devices. So even though theoretically iteration and recursion are equivalent, practically speaking, it makes a big difference. $\endgroup$ – Aryabhata Oct 7 '10 at 17:10
  • $\begingroup$ @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. $\endgroup$ – e.James Oct 7 '10 at 17:13
  • 2
    $\begingroup$ @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 :) $\endgroup$ – e.James Oct 7 '10 at 17:21

No longer relevant, keeping answer around for comments.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – e.James Oct 7 '10 at 17:10
  • $\begingroup$ @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? $\endgroup$ – Aryabhata Oct 7 '10 at 17:12
  • $\begingroup$ @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. $\endgroup$ – e.James Oct 7 '10 at 17:16
  • $\begingroup$ @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? $\endgroup$ – Aryabhata Oct 7 '10 at 17:23
  • $\begingroup$ @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! $\endgroup$ – e.James Oct 7 '10 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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