# Is there a simple function which can be used to determine the two “next” search indexes in a binary search?

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

-
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
@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
@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

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