leetcode

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

0034.cpp (1011B)

      1 class Solution {
      2     int binary_search_left(const vector<int> &nums, int target) {
      3         int low = 0, high = nums.size() - 1;
      4         while (low <= high) {
      5             int mid = low + (high - low) / 2;
      6             if (nums[mid] >= target)
      7                 high = mid - 1;
      8             else
      9                 low = mid + 1;
     10         }
     11         return low;
     12     }
     13 
     14     int binary_search_right(const vector<int> &nums, int target) {
     15         int low = 0, high = nums.size() - 1;
     16         while (low <= high) {
     17             int mid = low + (high - low) / 2;
     18             if (nums[mid] <= target)
     19                 low = mid + 1;
     20             else
     21                 high = mid - 1;
     22         }
     23         return high;
     24     }
     25 
     26   public:
     27     vector<int> searchRange(const vector<int> &nums, const int target) {
     28         const int low = binary_search_left(nums, target);
     29         if (low >= nums.size() || nums[low] != target) return {-1, -1};
     30         const int high = binary_search_right(nums, target);
     31         return {low, high};
     32     }
     33 };