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

1

No longer relevant, keeping answer around for comments.

  • 0
    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.2010-10-07
  • 0
    @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?2010-10-07
  • 0
    @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.2010-10-07
  • 0
    @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?2010-10-07
  • 0
    @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!2010-10-07
  • 0
    @e.James: Binary search on array is much more clear than talking about indices in binary trees which do not even exist.2010-10-07
  • 0
    @e.James: May I ask why you want to do this? What kind of speed up you think this will gain you? i.e. what scenario will you use it in?2010-10-07
  • 0
    @Moron: In this application, processing time is *far* more scarce than code space. Since the high and low branches of the binary search are always the same for a given node, I want to move the index calculation out of the runtime and encode it statically in the constant table. The speed gain is ~25%. I am working in assembly with a RISC processor, so I know *exactly* how long things will take.2010-10-07
  • 0
    @e.James: If the high/low index calculation is not part of runtime then why do you even want a non recursive version? Why not just do the calculation when creating the data table? btw, have you heard of perfect hashing? This is hashing for values known before hand, and will give you _worst case_ O(1) time lookup and should be faster than binary search.2010-10-07
  • 0
    @Moron: I *am* doing the calculation when creating the data table. That's what led to this question in the first place. I want a simple function that I can use, per line of the data table, that produces the necessary high and low indexes. Of course I can build the whole binary tree and then extract all the indexes, but I'm looking for a more elegant solution.2010-10-07
  • 0
    @Moron: perfect hashing sounds *very* interesting. Thank you for the tip. I'm reading up on it now.2010-10-07
  • 0
    @e.James: I would say that building the binary tree is an elegant solution. It is O(N), and in fact, the binary tree solution is very flexible. For instance, say some nodes had more probability of being looked up than others, you could then build a "skewed" binary tree catering to that etc.2010-10-07
  • 0
    That may be true, but it leaves me no closer to an answer here. We have gotten ourselves bogged down in the technical side of this discussion, and for that I am sorry. I asked this question here instead of StackOverflow because I think there could be a mathematical answer.2010-10-07
  • 0
    @e.James: Yes, I understand why you chose this site. You are looking for a simple mathematical formula which can probably be translated into an O(1) algorithm. Unfortunately, your question does not really make it clear what you are looking for. It is too verbose. Right now there is too much irrelevant information which is meaningless to non-programmers (and misleading {like asking for non-recursive} to programmers!). I suggest you edit it to make it smaller and to the point.2010-10-07
  • 0
    @Moron: I have simplified the question, and tried to remove all programming terminology. Hopefully that helps. I appreciate all of your suggestions.2010-10-07
  • 0
    @Moron: Your assumption about my choice of forum is incorrect. I have a clunky recursive solution that works fine, especially since it is done outside of the runtime. I posted here because working on the problem made me curious about a strictly mathematical solution.2010-10-07