查找高/低数字的算法,最多1.5n比较

Question

我现在一直在考虑这个家庭作业问题.给定大小为n的数组,设计一种算法,该算法将找到最高1.5n比较的高值和低值.

我的第一次尝试是

int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted

for (i=0, i < n, i++) {
  if (numList[i] > high)
    high = numList[i]

  else if (numList[i] < low)
    low = numList[i]

}

我的问题是循环的每次迭代都有三种可能性之一:

• 发现低值 - 进行了1次比较
• 找到了很高的价值 - 进行了2次比较
• 两者都没有找到 - 进行了2次比较

因此,对于整个数组遍历,最多可以进行2n次比较,这与1.5n比较的问题最大要求相差甚远.

Answer 1

从一对数字开始,找到本地最小值和最大值(n/2比较).接下来,从n/2个局部最大值(n/2个比较)中找到全局最大值,并从局部分钟(n/2个比较)中找到类似的全局最小值.总比较:3*n/2!

For i in 0 to n/2: #n/2 comparisons
    if x[2*i]>x[2*i+1]:
        swap(x,2*i,2*i+1)

global_min = min( x[0], x[2], ...) # n/2 comparisons
global_max = max( x[1], x[3], ...) # n/2 comparisons

请注意,上述解决方案会更改阵列.替代解决方案:

Initialize min and max
For i = 0 to n/2:
    if x[2*i]<x[2*i+1]:
        if x[2*i]< min:
            min = x[2*i]
        if x[2*i+1]> max:
            max = x[2*i+1]
    else:
        if x[2*i+1]< min:
            min = x[2*i+1]
        if x[2*i]> max:
            max = x[2*i]