leetcode

commit 283a31b1e87c9ed6c7445084e0f292a91d80f2bb
parent 5fd55bcf1031021e7ce5dba8f0e8fb833a9d7262
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 21 Jan 2023 16:04:52 +0100

Algorithm I: Day 1

Diffstat:
A
Problems/0035.cpp
 | 
15
+++++++++++++++
A
Problems/0278.cpp
 | 
17
+++++++++++++++++
A
Problems/0704.cpp
 | 
15
+++++++++++++++
M
README.md
 | 
3
+++

4 files changed, 50 insertions(+), 0 deletions(-)
diff --git a/Problems/0035.cpp b/Problems/0035.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  int searchInsert(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;
+      if (nums[mid] < target)
+        low = mid + 1;
+      else
+        high = mid - 1;
+    }
+    return high + 1;
+  }
+};
diff --git a/Problems/0278.cpp b/Problems/0278.cpp
@@ -0,0 +1,17 @@
+// The API isBadVersion is defined for you.
+// bool isBadVersion(int version);
+
+class Solution {
+public:
+  int firstBadVersion(int n) {
+    int low = 1, high = n, last = -1;
+    while (low <= high) {
+      int mid = low + (high - low) / 2;
+      if (isBadVersion(mid))
+        high = (last = mid) - 1;
+      else
+        low = mid + 1;
+    }
+    return last;
+  }
+};
diff --git a/Problems/0704.cpp b/Problems/0704.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  int search(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;
+      if (nums[mid] < target)
+        low = mid + 1;
+      else
+        high = mid - 1;
+    }
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -38,6 +38,7 @@ for solving problems.
 |  0026  |    Easy    | [Remove Duplicates from Sorted Array](Problems/0026.cpp)                                         |
 |  0027  |    Easy    | [Remove Element](Problems/0027.cpp)                                                              |
 |  0028  |   Medium   | [Find the Index of the First Occurrence in a String](Problems/0028.cpp)                          |
+|  0035  |    Easy    | [Search Insert Position](Problems/0035.cpp)                                                      |
 |  0036  |   Medium   | [Valid Sudoku](Problems/0036.cpp)                                                                |
 |  0043  |   Medium   | [Multiply Strings](Problems/0043.cpp)                                                            |
 |  0049  |   Medium   | [Group Anagrams](Problems/0049.cpp)                                                              |
@@ -120,6 +121,7 @@ for solving problems.
 |  0242  |    Easy    | [Valid Anagram](Problems/0242.cpp)                                                               |
 |  0257  |    Easy    | [Binary Tree Paths](Problems/0257.cpp)                                                           |
 |  0263  |    Easy    | [Ugly Number](Problems/0263.cpp)                                                                 |
+|  0278  |    Easy    | [First Bad Version](Problems/0278.cpp)                                                           |
 |  0279  |   Medium   | [Perfect Squares](Problems/0279.cpp)                                                             |
 |  0283  |    Easy    | [Move Zeroes](Problems/0283.cpp)                                                                 |
 |  0287  |   Medium   | [Find the Duplicate Number](Problems/0287.cpp)                                                   |
@@ -185,6 +187,7 @@ for solving problems.
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                        |
 |  0700  |    Easy    | [Search in a Binary Search Tree](Problems/0700.cpp)                                              |
 |  0701  |   Medium   | [Insert into a Binary Search Tree](Problems/0701.cpp)                                            |
+|  0704  |    Easy    | [Binary Search](Problems/0704.cpp)                                                               |
 |  0707  |   Medium   | [Design Linked List](Problems/0707.cpp)                                                          |
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                            |
 |  0733  |    Easy    | [Flood Fill](Problems/0733.cpp)                                                                  |