Question

How to search insert position of K in a sorted vector with C++

Answer 1

// Given a sorted array/vector of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

#include <iostream>
#include <vector>

// Function to find the index of k or the position 
int searchInsertPositionOfK(std::vector<int> vec, int k) {  

    for(int i = 0; i < vec.size(); i++) {  

        // If k is found or needs to be inserted before arr[i]
        if (vec[i] >= k) {  
            return i;  
        }  
    }  

    // If k is greater than all elements, it should be inserted at the end
    return vec.size();  
}  

int main() {  
   
    std::vector<int> vec1 = {1, 3, 5, 6, 7, 8};  
    int k1 = 5;  
    std::cout << searchInsertPositionOfK(vec1, k1) << "\n";  
    
    std::vector<int> vec2 = {1, 3, 5, 6, 7, 8};  
    int k2 = 2;  
    std::cout << searchInsertPositionOfK(vec2, k2) << "\n";  
    
    std::vector<int> vec3 = {1, 3, 5, 6, 7, 8};  
    int k3 = 9;  
    std::cout << searchInsertPositionOfK(vec3, k3) << "\n";  
}
 
 
 
/*
run:
 
2
1
6
 
*/
   
 

 

70+ SQL courses for beginners and professionals

Answer 2

// Given a sorted array/vector of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

#include <iostream>
#include <vector>

// Function to find the index of k or the position - Using Binary Search
int searchInsertPositionOfK(std::vector<int> vec, int k) {  

    int left = 0, right = vec.size() - 1;  

    while (left <= right) {  

        int mid = left + (right - left) / 2;  

        if (vec[mid] == k) {  
            return mid;  
        }  

        // If k is smaller, search in the left half
        else if (vec[mid] > k) {
            right = mid - 1;  
        }  

        // If k is larger, search in the right half
        else {  
            left = mid + 1;  
        }  
    }  

    // If k is not found, it should be inserted at the end
    return left;  
}  

int main() {  
   
    std::vector<int> vec1 = {1, 3, 5, 6, 7, 8};  
    int k1 = 5;  
    std::cout << searchInsertPositionOfK(vec1, k1) << "\n";  
    
    std::vector<int> vec2 = {1, 3, 5, 6, 7, 8};  
    int k2 = 2;  
    std::cout << searchInsertPositionOfK(vec2, k2) << "\n";  
    
    std::vector<int> vec3 = {1, 3, 5, 6, 7, 8};  
    int k3 = 9;  
    std::cout << searchInsertPositionOfK(vec3, k3) << "\n";  
}
 
 
 
/*
run:
 
2
1
6
 
*/

 

70+ SQL courses for beginners and professionals