我正在尝试制作一个算法,找到将目标插入已排序数组的最佳位置。
目标是返回项目在列表中存在的位置,否则返回它会进入的位置以保持列表排序。
所以说,假设我有一个列表:
0 1 2 3 4 5 6
---------------------------------
| 1 | 2 | 4 | 9 | 10 | 39 | 100 |
---------------------------------
我的目标项是14
,它应该返回5
的索引位置。
我目前拥有的伪代码:
array = generateSomeArrayOfOrderedNumbers()
number findBestIndex(target, start, end)
mid = abs(end - start) / 2
if (mid < 2)
// Not really sure what to put here
return start + 1 // ??
if (target < array[mid])
// The target belongs on the left side of our list //
return findBestIndex(target, start, mid - 1)
else
// The target belongs on the right side of our list //
return findBestIndex(target, mid + 1, end)
我不太确定应该在这个时候放什么。我试图用二分搜索的方法来解决这个问题,但是经过五次重写后,这是我能想到的最好的解决方案。
if
)。只需将基本情况设置为start > end
,并根据比较递归到[start,mid]
或[mid + 1,end]
。请记住,我们不想找到target
,而是要找到target
的后继者。 - Niklas B.