# 1095. Find in Mountain Array     • Time: $O(\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 /** * // This is the MountainArray's API interface. * // You should not implement it, or speculate about its implementation * class MountainArray { * public: * int get(int index); * int length(); * }; */ class Solution { public: int findInMountainArray(int target, MountainArray& mountainArr) { const int n = mountainArr.length(); const int peakIndex = peakIndexInMountainArray(mountainArr, 0, n - 1); const int leftIndex = searchLeft(mountainArr, target, 0, peakIndex); if (mountainArr.get(leftIndex) == target) return leftIndex; const int rightIndex = searchRight(mountainArr, target, peakIndex + 1, n - 1); if (mountainArr.get(rightIndex) == target) return rightIndex; return -1; } private: // 852. Peak Index in a Mountain Array int peakIndexInMountainArray(MountainArray& A, int l, int r) { while (l < r) { const int m = (l + r) / 2; if (A.get(m) < A.get(m + 1)) l = m + 1; else r = m; } return l; } int searchLeft(MountainArray& A, int target, int l, int r) { while (l < r) { const int m = (l + r) / 2; if (A.get(m) < target) l = m + 1; else r = m; } return l; } int searchRight(MountainArray& A, int target, int l, int r) { while (l < r) { const int m = (l + r) / 2; if (A.get(m) > target) l = m + 1; else r = m; } return l; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 /** * // This is MountainArray's API interface. * // You should not implement it, or speculate about its implementation * interface MountainArray { * public int get(int index) {} * public int length() {} * } */ class Solution { public int findInMountainArray(int target, MountainArray mountainArr) { final int n = mountainArr.length(); final int peakIndex = peakIndexInMountainArray(mountainArr, 0, n - 1); final int leftIndex = searchLeft(mountainArr, target, 0, peakIndex); if (mountainArr.get(leftIndex) == target) return leftIndex; final int rightIndex = searchRight(mountainArr, target, peakIndex + 1, n - 1); if (mountainArr.get(rightIndex) == target) return rightIndex; return -1; } // 852. Peak Index in a Mountain Array private int peakIndexInMountainArray(MountainArray A, int l, int r) { while (l < r) { final int m = (l + r) / 2; if (A.get(m) < A.get(m + 1)) l = m + 1; else r = m; } return l; } private int searchLeft(MountainArray A, int target, int l, int r) { while (l < r) { final int m = (l + r) / 2; if (A.get(m) < target) l = m + 1; else r = m; } return l; } private int searchRight(MountainArray A, int target, int l, int r) { while (l < r) { final int m = (l + r) / 2; if (A.get(m) > target) l = m + 1; else r = m; } return l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 # """ # 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: n = mountain_arr.length() peakIndex = self.peakIndexInMountainArray(mountain_arr, 0, n - 1) leftIndex = self.searchLeft(mountain_arr, target, 0, peakIndex) if mountain_arr.get(leftIndex) == target: return leftIndex rightIndex = self.searchRight(mountain_arr, target, peakIndex + 1, n - 1) if mountain_arr.get(rightIndex) == target: return rightIndex return -1 # 852. Peak Index in a Mountain Array def peakIndexInMountainArray(self, A: 'MountainArray', l: int, r: int) -> int: while l < r: m = (l + r) // 2 if A.get(m) < A.get(m + 1): l = m + 1 else: r = m return l def searchLeft(self, A: 'MountainArray', target: int, l: int, r: int) -> int: while l < r: m = (l + r) // 2 if A.get(m) < target: l = m + 1 else: r = m return l def searchRight(self, A: 'MountainArray', target: int, l: int, r: int) -> int: while l < r: m = (l + r) // 2 if A.get(m) > target: l = m + 1 else: r = m return l