leetcode

commit acc6c1c69800fcfc384f1ac7b5f4272239dddff3
parent b1114320c2caa1beac3da908193ad3533950b480
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sat, 15 Apr 2023 20:29:57 -0500

Search insert position binary search

Diffstat:
A
search-insert-position/search-insert-position.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

1 file changed, 43 insertions(+), 0 deletions(-)
diff --git a/search-insert-position/search-insert-position.cpp b/search-insert-position/search-insert-position.cpp
@@ -0,0 +1,43 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+//Use a binary search to find where the next value would be inserted and return that index.
+//Speed: 3ms Beats: 88.82%
+//Memory: 9.7MB Beats: 80.21%
+int searchInsert(vector<int>& nums, int target) {
+    
+
+    if(target > nums[nums.size() - 1]){
+        return nums.size();
+    }
+    if(target <= nums[0]){
+        return 0;
+    }
+
+    int upper_bound = nums.size() - 1;
+    int lower_bound = 0;
+    while(true){
+        int curr_val = nums[(upper_bound + lower_bound) / 2];
+        if(target == curr_val){
+            return (upper_bound + lower_bound) / 2;
+        }
+        else if(target > curr_val){
+            lower_bound = (upper_bound + lower_bound) / 2;
+        }
+        else if(target < curr_val){
+            upper_bound = (upper_bound + lower_bound) / 2;
+        }
+        
+        if(upper_bound == lower_bound + 1){
+            return upper_bound;
+        }
+    }
+    return 0;
+
+}
+
+int main(){
+    vector<int> vec = {0 , 1 , 3, 4 ,5 ,6 ,7 ,8 , 8 , 8 , 100};
+    searchInsert(vec, 4);
+}