leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

search-insert-position.dart (1274B)

      1 //Find the position to insert a value in a sorted list
      2 //My implementation uses a binary search to find the position
      3 //and returns the index. The time complexity of this code is
      4 //O(log(n)) where n is the number of elemnents in the nums list.
      5 //Time: 281ms Beats: 56.18%
      6 //Memory: 143.8MB Beats: 17.13%
      7 
      8 class Solution {
      9   int searchInsert(List<int> nums, int target) {
     10       if(target > nums[nums.length - 1]){
     11           return nums.length;
     12       }
     13       if(target <= nums[0]){
     14           return 0;
     15       }
     16       int upper_bound = nums.length - 1;
     17       int lower_bound = 0;
     18       while(true){
     19           int median = ((upper_bound + lower_bound ) / 2).toInt();
     20           if(upper_bound - lower_bound == 1){
     21               if(nums[upper_bound] == target){
     22                   return upper_bound;
     23               }
     24               else if(nums [lower_bound] == target){
     25                   return lower_bound;
     26               }
     27               else{
     28                   return upper_bound;
     29               }
     30           }
     31           if(nums[median] > target){
     32               upper_bound = median;
     33           }
     34           else if(nums[median] < target){
     35               lower_bound = median;
     36           }
     37           else if(nums[median] == target){
     38               return median;
     39           }
     40       }
     41   }
     42 }