leetcode

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

search-insert-position.cpp (1061B)

      1 #include <iostream>
      2 #include <vector>
      3 using namespace std;
      4 
      5 //Use a binary search to find where the next value would be inserted and return that index.
      6 //Speed: 3ms Beats: 88.82%
      7 //Memory: 9.7MB Beats: 80.21%
      8 int searchInsert(vector<int>& nums, int target) {
      9     
     10 
     11     if(target > nums[nums.size() - 1]){
     12         return nums.size();
     13     }
     14     if(target <= nums[0]){
     15         return 0;
     16     }
     17 
     18     int upper_bound = nums.size() - 1;
     19     int lower_bound = 0;
     20     while(true){
     21         int curr_val = nums[(upper_bound + lower_bound) / 2];
     22         if(target == curr_val){
     23             return (upper_bound + lower_bound) / 2;
     24         }
     25         else if(target > curr_val){
     26             lower_bound = (upper_bound + lower_bound) / 2;
     27         }
     28         else if(target < curr_val){
     29             upper_bound = (upper_bound + lower_bound) / 2;
     30         }
     31         
     32         if(upper_bound == lower_bound + 1){
     33             return upper_bound;
     34         }
     35     }
     36     return 0;
     37 
     38 }
     39 
     40 int main(){
     41     vector<int> vec = {0 , 1 , 3, 4 ,5 ,6 ,7 ,8 , 8 , 8 , 100};
     42     searchInsert(vec, 4);
     43 }