aboutsummaryrefslogtreecommitdiff
path: root/trim_binary_tree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'trim_binary_tree.cpp')
-rw-r--r--trim_binary_tree.cpp47
1 files changed, 47 insertions, 0 deletions
diff --git a/trim_binary_tree.cpp b/trim_binary_tree.cpp
new file mode 100644
index 0000000..3f4168a
--- /dev/null
+++ b/trim_binary_tree.cpp
@@ -0,0 +1,47 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<int> searchRange(vector<int> &nums, int target) {
+ int s = 0, e = nums.size() - 1;
+ vector<int> ans(2, -1);
+ // first position
+ while (s <= e) {
+ int m = s + (e - s) / 2;
+ if (nums[m] < target)
+ s = m + 1;
+ else if (nums[m] > target)
+ e = m - 1;
+ else {
+ if (m == s || nums[m] != nums[m - 1]) {
+ ans[0] = m;
+ break;
+ } else {
+ e = m - 1;
+ ans[0] = m - 1;
+ }
+ }
+ }
+ // second position
+ s = 0, e = nums.size() - 1;
+ while (s <= e) {
+ int m = s + (e - s) / 2;
+ if (nums[m] < target)
+ s = m + 1;
+ else if (nums[m] > target)
+ e = m - 1;
+ else {
+ if (m == e || nums[m] != nums[m + 1]) {
+ ans[1] = m;
+ break;
+ } else {
+ s = m + 1;
+ ans[1] = m + 1;
+ }
+ }
+ }
+ return ans;
+ }
+};
+
+int main() {}