查找增加后减小列表的最大值和最小值 [英] Find the max and min of an increasing then decreasing list

问题描述

我试图使用Google的这一次没有成功......我敢肯定有一个技术名称为这个问题还是喜欢它的问题，但我似乎无法找到答案。

给出一个列表→整数，即严格递增，然后严格递减，发现该名单的最大值和最小值。

因此​​，例如，→可能是 {1 2 3 4 5 4 3 2} 或 {2 4 5 7 3} 。

有关发现的最小的，我说的最小整数不得不要么是左或右的端点，所以才比较端点，并返回最小的一个，给一定的时间。

有关发现的最大，我认为基本上是一个递归二进制搜索找到点 L [X] ，使得 L [X]＆GT; L [X-1] 和 L [X]＆GT; L [X + 1] ，给摊销LG电子（n）的时间。他似乎不喜欢这个答案，这似乎相当幼稚的我，所以我不知道是否有什么我失踪。

感谢您的帮助！

编辑：

我在Python的解决方案：

 高清马克斯（L）：
    N = LEN（L）-1
    如果n == 0：
        返回L [0]

    如果L [N / 2]≥ L [N / 2  -  1]和L [n / 2个]≥ L [N / 2 + 1]：
        返回L [N / 2]
    ELIF L [N / 2]其中， L [N / 2 + 1]：
        返回最大（L [N / 2]）
    其他：
        返回最大（L [N / 2]）
 

解决方案

我假设列表的意图是一个数组 - 否则它只是线性搜索，因为DeepYellow指出。

一个稍微不同的战略应能在找到最大需要比较的一半的平均数目削减。该策略是确定在列表中某些条件的间隔：一个左端点，右端点，和一个中点，与列表值在中点大于在两个端点。这种结构---中点最高具有两个包围点限定的时间间隔---是不变建立和preserve在搜索中。调用中点的电流最大的。

要建立不变，最初端点可以只是列表的末端。检查连线的中点处的列表值。如果是大于在终端，这些将被罚款作为起点进行搜索。否则，递归走要么留一半（如果中点比左点较低的值）或右半部分（如果中点比右点的较低值）的名单，并再次检查的中点。

以实现搜索，首先检查间隔的左半部分的中点。如果这是大于previous中点，乘previous中点作为定义间隔的右侧端点和新中点作为当前最大如果左边中点小于当前的最大，做同样的事情与间隔的右半部。如果有合适的中点越大，则对中点成为当前最大和老中点成为新的左端点。否则，当前最大值是不变的，但离开中点成为新的左端点，右中点成为新的左端点。

在平均，你会得到左边一半的时间在新的中点，以1/3多比较，否则就需要2/3尽可能多比较。平均来说，一半的。

下面是用Python实现：

 高清find_max（LST，出借，MIDP，分割）：
    断言LST [放贷] LT; LST [MIDP]和LST [撕裂] LT; LST [MIDP]，\
        不变侵犯，无效的序列

    LMID =（贷款+ MIDP）// 2
    RMID =（雷德+ MIDP + 1）// 2

    如果贷款+ 2 ==裂：
        回报MIDP
    ELIF LST [LMID] GT; LST [MIDP]：
        返回find_max（LST，出借，LMID，MIDP）
    ELIF LST [RMID] GT; LST [MIDP]：
        返回find_max（LST，MIDP，RMID，分割）
    其他：
        返回find_max（LST，LMID，MIDP，RMID）

高清init_invariant（LST，出借，分割）：
    声称借给+ 1＆LT;撕裂，不变侵犯，无效的序列

    MIDP =（贷款+撕裂）// 2

    如果LST [MIDP] LT; LST [放贷]：
        返回init_invariant（LST，出借，MIDP）
    ELIF LST [MIDP] LT; LST [撕裂]：
        返回init_invariant（LST，MIDP，分割）
    其他：
        回出借，MIDP，裂

高清最大化（LST）：
    出借，MIDP，雷德= init_invariant（LST，0，len个（LST）-1）
    返回find_max（LST，出借，MIDP，分割）
 

I've tried googling for this one without much success...I'm sure there's a technical name for this problem or for problems like it, but I can't seem to find the answer.

Given a list L of integers, that is strictly increasing, and then strictly decreasing, find the maximum and minimum of that list.

So for example, L might be {1 2 3 4 5 4 3 2} or {2 4 5 7 3}.

For finding the minimum, I said that the smallest integer had to either be the left or the right endpoint, so just compare the endpoints, and return the smallest one, giving constant time.

For finding the maximum, I suggested basically a recursive binary search to find the point L[x] such that L[x] > L[x-1] and L[x] > L[x+1], giving amortized lg(n) time. He didn't seem to love that answer, and it does seem rather naive to me, so I'm wondering if there's something I'm missing.

Thanks for the help!

edit:

My solution in python:

def Max(L):
    n = len(L)-1
    if n == 0:
        return L[0]

    if L[n/2] > L[n/2 - 1] and L[n/2] > L[n/2 + 1]:
        return L[n/2]
    elif L[n/2] < L[n/2 + 1]:
        return Max(L[n/2:])
    else:
        return Max(L[:n/2])  

解决方案

I'll assume that list is intended to be an array---otherwise it's just linear search, as DeepYellow pointed out.

A slightly different strategy should be able to cut in half the average number of comparisons needed to find the max. The strategy is to identify an interval in the list with certain conditions: a left endpoint, a right endpoint, and a midpoint, with list value at the midpoint greater than at either endpoint. This structure---midpoint highest with two bracketing points defining the interval---is an invariant to establish and preserve in the search. Call the midpoint the current max.

To establish the invariant, the initial endpoints can just be the ends of the list. Check the list value at the midpoint. If it's greater than at the endpoints, those will be fine as starting points for the search. Otherwise, recursively take either the left half (if the midpoint has a lower value than the left point) or right half (if the midpoint has a lower value than the right point) of the list and check the midpoint again.

To effectuate the search, first check the midpoint of the left half of the interval. If this is greater than the previous midpoint, take the previous midpoint as defining the right endpoint of the interval and the new midpoint as the current max. If the left midpoint is less than the current max, do the same thing with the right half of the interval. If the right midpoint is greater, then the right midpoint becomes the current max and the old midpoint becomes the new left endpoint. Otherwise, the current max is unchanged, but the left midpoint becomes the new left endpoint and the right midpoint becomes the new left endpoint.

On average, you'll get the new midpoint on the left half the time, taking 1/3 as many comparisons, otherwise it takes 2/3 as many comparison. On average, half as many.

Here's an implementation in Python:

def find_max(lst, lend, midp, rend):
    assert lst[lend] < lst[midp] and lst[rend] < lst[midp], \
        "Invariant violated, invalid sequence"

    lmid = (lend + midp) // 2
    rmid = (rend + midp + 1) // 2

    if lend + 2 == rend:
        return midp
    elif lst[lmid] > lst[midp]:
        return find_max(lst, lend, lmid, midp)
    elif lst[rmid] > lst[midp]:
        return find_max(lst, midp, rmid, rend)
    else:
        return find_max(lst, lmid, midp, rmid)

def init_invariant(lst, lend, rend):
    assert lend + 1 < rend, "Invariant violated, invalid sequence"

    midp = (lend + rend) // 2

    if lst[midp] < lst[lend]:
        return init_invariant(lst, lend, midp)
    elif lst[midp] < lst[rend]:
        return init_invariant(lst, midp, rend)
    else:
        return lend, midp, rend

def maximize(lst):
    lend, midp, rend = init_invariant(lst, 0, len(lst)-1)
    return find_max(lst, lend, midp, rend)

这篇关于查找增加后减小列表的最大值和最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！