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

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

# """

# This is MountainArray's API interface.

# You should not implement it, or speculate about its implementation

# """

#class MountainArray:

#    def get(self, index: int) -> int:

#    def length(self) -> int:

class Solution:

    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:

        l, r = 0, mountain_arr.length()

        while l + 2 < r:

            p, q = (l + r)//2, (l + r)//2 + 1

            fp, fq = mountain_arr.get(p), mountain_arr.get(q)

            if fp < fq:

                l = p

            else:

                r = q

        crit, val = l, mountain_arr.get(l)

        for i in range(l+1, min(r+1, mountain_arr.length())):

            fi = mountain_arr.get(i)

            if fi > val:

                crit, val = i, fi

        if val == target:

            return crit

        l, r = 0, crit

        if mountain_arr.get(l) == target:

            return l

        while l + 1 < r:

            m = (l + r)//2

            fm = mountain_arr.get(m)

            if fm >= target:

                r = m

            else:

                l = m

        if mountain_arr.get(r) == target:

            return r

        l, r = crit, mountain_arr.length()-1

        while l + 1 < r:

            m = (l + r)//2

            fm = mountain_arr.get(m)

            if fm > target:

                l = m

            else:

                r = m

        if mountain_arr.get(r) == target:

            return r

        return -1

너무 쓰레기 같이 풀었다 반성해야지