Let’s say you have N integers from 1:N (i.e. N = 15)

```
cur_vector = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ]
```

What is the most minimal way to turn this into the breadth-first search indices from recursive bisection?

i.e.

```
# assuming a breadth_indices func
> println( breadth_indices( cur_vector ) )
[ 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 ]
```

Pictorially,

,

This is the best I could come up with:

```
function breadth_indices(num_points::Number)
cur_indices = []
cur_step = num_points
while length(cur_indices) < num_points - 1
cur_step = Int(floor( (cur_step-1) / 2 )) + 1
for cur_index in 1:num_points-1
iszero( cur_index % cur_step ) || continue
in(cur_index, cur_indices) && continue
push!(cur_indices, cur_index)
end
end
push!(cur_indices, num_points)
cur_indices
end
```

Then you can have fun with it, by reordering vectors:

```
function bisect_reorder!(cur_vector::Vector)
cur_indices = breadth_indices(length(cur_vector))
cur_vector .= cur_vector[cur_indices]
end
```

For an example of how this works:

```
> cur_points = collect( linspace(0, 1, 11) )
> bisect_reorder!(cur_points)
[
0.5
0.2
0.8
0.1
0.3
0.7
0.9
0.0
0.4
0.6
1.0
]
```

A sister function of this would be your outward-in reordering:

```
function out_in_reorder!(cur_vector::Vector)
cur_indices = centering_indices(length(cur_vector))
cur_vector .= cur_vector[cur_indices]
end
function centering_indices(num_points::Number)
cur_indices = []
cur_half_point = Int(floor(num_points/2))
for cur_index in 1:cur_half_point
push!(cur_indices, cur_index)
push!(cur_indices, num_points-(cur_index-1))
end
isodd(num_points) && push!(cur_indices, cur_half_point+1)
cur_indices
end
```

An analogous example to the one above is:

```
> cur_points = collect( linspace(0, 1, 11) )
> out_in_reorder!(cur_points)
[
0.0
1.0
0.1
0.9
0.2
0.8
0.3
0.7
0.4
0.6
0.5
]
```

```
function collect_bisection_indexes!(ix, level, a, b)
a ≤ b || return
mid = (a+b) ÷ 2
push!(ix, level => mid)
collect_bisection_indexes!(ix, level + 1, a, mid - 1)
collect_bisection_indexes!(ix, level + 1, mid + 1, b)
end
function bisection_indexes(n)
ix = Vector{Pair{Int,Int}}()
sizehint!(ix, n)
collect_bisection_indexes!(ix, 0, 1, n)
last.(sort!(ix, by = first))
end
bisection_indexes(15)
```

1 Like

Functional version:

```
function collect_bisection_indexes(level, a, b)
a ≤ b || return Vector{Tuple{Int,Int}}()
mid = (a+b) ÷ 2
vcat([level => mid],
collect_bisection_indexes(level + 1, a, mid - 1),
collect_bisection_indexes(level + 1, mid + 1, b))
end
function bisection_indexes(n)
ix = collect_bisection_indexes(0, 1, n)
last.(sort!(ix, by = first))
end
```

Implicitly, both of the above implementations rely on `sort!`

choosing a stable algorithm, which I believe it does, but it could be made explicit.