arrays - 遍历数组广度搜索

Question

问题的标题可能有点误导，但我不确定如何描述我的问题。

我想重构一个数组的键，这样循环将按照以下模式跳转:

示例 1:

keys from 1,2,3,4,5,6,7,8,9 will lead to 1,9,5,3,7,2,6,4,8

• 取第一个元素 - 1
• 取最后一个元素 - 9
• 取中间 (1+9)/2 = 5
• 去上半场取1和5-3的中间
• 跳到下半场取5和9-7中间
• 上半场跳回上半场取2
• 下半场跳回上半场取6
• 跳回上半场下半场取4
• 下半场跳回下半场取8

当然，这是一个理想化的例子，所有的东西都可以很好地分割。如果不是这种情况，则您必须设置 floor 和 ceil 才能划分新元素。

示例 2:

key from 1,2,3,4,5,6,7,8,9,10 will lead to 1,10,5,6,3,8,2,7,4,9

凭借我对算法和数据结构的了解，我尝试使用递归/分而治之，但我没能实现两半之间的跳跃。

所以我想我必须添加一些参数，比如分割的一半的长度和位置，但在这里我无法实现。

对我来说有趣的问题是:我的想法是否复杂，是否有更简单的解决方案？或者这个问题真的有这么复杂吗？

我很高兴收到有关文献或代码片段的任何建议来尝试。

谢谢和最好的问候斯蒂芬

Answer 1

我不确定你是否可以通过递归或分而治之的方式来实现这个算法。但是您可以使用广度优先搜索优雅地做到这一点。下面是 python 伪代码，其中有一个队列，其元素是间隔。

#initialize queue Q with the whole interval
n = len(your_list)

# breadth first search
Q.push([0, n-1])
while Q not empty:
    itv = q.pop_front()
    process(itv)     # print the middle element of interval itv, etc.
    itv_1, itv_2 = divide_interval_into_halves(itv)
    if len(itv_1) > 0:
        Q.push(itv_1)
    if len(itv_1) > 0:
        Q.push(itv_2)

希望对您有所帮助:)