leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1095.cpp (1491B)

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