Find the max and min of an increasing then decreasing list

Question

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])  

Answer 1

    #TC: O(logn)
    #SC: O(1)
    #Finding max value
        
    def IncDec(arr):
        low, high = 0 ,len(arr) - 1 
        
        while(low<=high):
            mid = (low+high)//2
            
            if (not mid or mid == len(arr)-1) or arr[mid-1] < arr[mid] > arr[mid+1]:
                return arr[mid]
            
            if arr[mid-1] < arr[mid] < arr[mid+1]:
                low = mid+1
            else:
                high = mid - 1
                
    if __name__=="__main__":
        arr = [6,9,15,25,35,50,41,29,23,8]
        print(IncDec(arr))

Answer 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)

Answer 3

Alright, looked it up, you have two options. The simpler one is the ternary search. The basic gist of it is, you find the two numbers 1/3 (x) and 2/3 (y) of the way through. If x < y, then the max can't be in the first third. If x > y, it can't be in the last third. Combine it with a simple check for a base case, and you've got yourself a recursive algorithm.

Now, it's still O(log(n)), so with half the comparisons per call, but only 2/3 the eliminations, you're really going from 2*log(base 2)(n) comparisons to 2*log(base 3)(n) comparisons. In theoretical terms, those are equivalent. In real terms, you're gaining, just not much, unless you don't have random access, e.g., for a function.

The more complicated one is the Fibonacci search. See also here. It's similar to the ternary search, except instead of just choosing 1/3 and 2/3 as your break points, there's a whole fancy process involving the Fibonacci numbers. It's still O(log(n)), so it's probably not worth the headache of implementation unless you don't have straight random access,.

Answer 4

If L is a list (in the usual sense of a linked list), then doing a binary search is slow since seeking to the ith element is O(N). I can't think of a faster way in that case than to return the first integer whose successor in the list is less than itself.

Edit:

Ok, so assuming that L is random access (as the poster requested in the comment below). You can't do a SIMPLE binary search because that requires that the list be sorted, which it is explicitly not. So binary search is clearly wrong--hence the interviewer's displeasure.

But you could be doing a binary search on a transformation of L given by:

T[i] = If L[i+1]-L[i] > 0 then 0 else 1

This transformed list is increasing and a search for the lower bound of the 1 elements indicates the correct index of L.

For example if L = {1 2 3 4 5 4 3 2}, then T = {0 0 0 0 1 1 1}

I am not advocating actually creating T, that would be silly. But the predicate of the binary search should be adjusted, and the range of the search should be shortened by one, since T has one less element than L.