leetcode

commit 90793ee4ccd515d2d80aa9453202ddd58023c962
parent d3a2c8adeac5d624ec69f230fadaaf31c74fe6a8
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Wed,  3 May 2023 08:25:22 -0500

Completed search insert position problem using dart

Diffstat:
A
search-insert-position/search-insert-position.dart
 | 
42
++++++++++++++++++++++++++++++++++++++++++

1 file changed, 42 insertions(+), 0 deletions(-)
diff --git a/search-insert-position/search-insert-position.dart b/search-insert-position/search-insert-position.dart
@@ -0,0 +1,42 @@
+//Find the position to insert a value in a sorted list
+//My implementation uses a binary search to find the position
+//and returns the index. The time complexity of this code is
+//O(log(n)) where n is the number of elemnents in the nums list.
+//Time: 281ms Beats: 56.18%
+//Memory: 143.8MB Beats: 17.13%
+
+class Solution {
+  int searchInsert(List<int> nums, int target) {
+      if(target > nums[nums.length - 1]){
+          return nums.length;
+      }
+      if(target <= nums[0]){
+          return 0;
+      }
+      int upper_bound = nums.length - 1;
+      int lower_bound = 0;
+      while(true){
+          int median = ((upper_bound + lower_bound ) / 2).toInt();
+          if(upper_bound - lower_bound == 1){
+              if(nums[upper_bound] == target){
+                  return upper_bound;
+              }
+              else if(nums [lower_bound] == target){
+                  return lower_bound;
+              }
+              else{
+                  return upper_bound;
+              }
+          }
+          if(nums[median] > target){
+              upper_bound = median;
+          }
+          else if(nums[median] < target){
+              lower_bound = median;
+          }
+          else if(nums[median] == target){
+              return median;
+          }
+      }
+  }
+}