leetcode

commit 5b33588e53ebdc8e59ad1ef729e7b489e1d78250
parent b2115756451ccfc1cbe355817eadb708be872f26
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon,  9 Oct 2023 22:00:37 +0000

Improved Daily Problem

Diffstat:
M
Problems/0034.cpp
 | 
31
+++++++++++++++++++------------

1 file changed, 19 insertions(+), 12 deletions(-)
diff --git a/Problems/0034.cpp b/Problems/0034.cpp
@@ -1,26 +1,33 @@
 class Solution {
-    int binary_search(const vector<int> &nums, int target) {
+    int binary_search_left(const vector<int> &nums, int target) {
         int low = 0, high = nums.size() - 1;
         while (low <= high) {
             int mid = low + (high - low) / 2;
-            if (nums[mid] == target)
-                return mid;
-            else if (nums[mid] > target)
+            if (nums[mid] >= target)
                 high = mid - 1;
             else
                 low = mid + 1;
         }
-        return -1;
+        return low;
+    }
+
+    int binary_search_right(const vector<int> &nums, int target) {
+        int low = 0, high = nums.size() - 1;
+        while (low <= high) {
+            int mid = low + (high - low) / 2;
+            if (nums[mid] <= target)
+                low = mid + 1;
+            else
+                high = mid - 1;
+        }
+        return high;
     }
 
   public:
-    vector<int> searchRange(vector<int> &nums, int target) {
-        int low, high;
-        low = high = binary_search(nums, target);
-        while (low - 1 >= 0 && nums[low - 1] == target)
-            low--;
-        while (high + 1 < nums.size() && nums[high + 1] == target)
-            high++;
+    vector<int> searchRange(const vector<int> &nums, const int target) {
+        const int low = binary_search_left(nums, target);
+        if (low >= nums.size() || nums[low] != target) return {-1, -1};
+        const int high = binary_search_right(nums, target);
         return {low, high};
     }
 };