Problem statement

https://leetcode.com/problems/find-in-mountain-array/

Solution

Let us break this problem into two subproblems: first one is to find peak point and the then find into two halves.

  1. To find peak point we can use binary search: we need to find the first point, where A[mid] < A[mid + 1]. See problem 0852. Peak Index in a Mountain Array. (There is also a way to do it with ternary search)
  2. For each of the parts use usual binary search.

Complexity

It is $O(\log n)$ for time and $O(1)$ for space.

Code

class Solution:
    def findInMountainArray(self, target, A):
        def search(beg, end, is_inc):
            while beg <= end:
                mid = (beg + end)//2
                cand = A.get(mid)
                if cand == target: return mid
                if (cand < target) == is_inc:
                    beg = mid + 1
                else:
                    end = mid - 1
            return float("inf")
        
        n = A.length()
        beg, end = 0, n - 1
        while beg < end:
            mid = (beg + end) // 2
            if A.get(mid) < A.get(mid + 1):
                beg = mid + 1
            else:
                end = mid
        
        q1 = search(0, beg, 1)
        q2 = search(beg, n - 1, 0)

        return min(q1, q2) if min(q1, q2) != float("inf") else -1