leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1095.cpp (1491B)

0 class Solution { 1 int find_peak(MountainArray &mountainArr) { 2 int left = 1, right = mountainArr.length() - 2; 3 while (left != right) { 4 const int mid = left + (right - left) / 2; 5 if (mountainArr.get(mid) < mountainArr.get(mid + 1)) 6 left = mid + 1; 7 else 8 right = mid; 9 } 10 return left; 11 } 12 13 int find_left(MountainArray &mountainArr, int left, int right, int target) { 14 while (left != right) { 15 const int mid = left + (right - left) / 2; 16 if (mountainArr.get(mid) < target) 17 left = mid + 1; 18 else 19 right = mid; 20 } 21 return left; 22 } 23 24 int find_right(MountainArray &mountainArr, int left, int right, int target) { 25 while (left != right) { 26 const int mid = left + (right - left) / 2; 27 if (mountainArr.get(mid) > target) 28 left = mid + 1; 29 else 30 right = mid; 31 } 32 return left; 33 } 34 35 public: 36 int findInMountainArray(int target, MountainArray &mountainArr) { 37 const int peak = find_peak(mountainArr); 38 39 const int left = find_left(mountainArr, 0, peak, target); 40 if (mountainArr.get(left) == target) return left; 41 42 const int right = find_right(mountainArr, peak + 1, mountainArr.length() - 1, target); 43 if (mountainArr.get(right) == target) return right; 44 45 return -1; 46 } 47 };