Question

How to search insert position of K in a sorted array 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 <stdio.h>

// Function to find the index of k or the position where it should be inserted
int searchInsertPositionOfK(int arr[], int size, int k) {
    for (int i = 0; i < size; i++) {
        // If k is found or needs to be inserted before arr[i]
        if (arr[i] >= k) {
            return i;
        }
    }
    // If k is greater than all elements, it should be inserted at the end
    return size;
}

int main() {
    int arr1[] = {1, 3, 5, 6, 7, 8};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 5;
    printf("%d\n", searchInsertPositionOfK(arr1, size1, k1));

    int arr2[] = {1, 3, 5, 6, 7, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 2;
    printf("%d\n", searchInsertPositionOfK(arr2, size2, k2));

    int arr3[] = {1, 3, 5, 6, 7, 8};
    int size3 = sizeof(arr3) / sizeof(arr3[0]);
    int k3 = 9;
    printf("%d\n", searchInsertPositionOfK(arr3, size3, k3));

    return 0;
}



   
/*
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 <stdio.h>

// Function to find the index of k or the position where it should be inserted - Using Binary Search
int searchInsertPositionOfK(int arr[], int size, int k) {
     int left = 0, right = size- 1;  
 
    while (left <= right) {  
 
        int mid = left + (right - left) / 2;  
 
        if (arr[mid] == k) {  
            return mid;  
        }  
 
        // If k is smaller, search in the left half
        else if (arr[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() {
    int arr1[] = {1, 3, 5, 6, 7, 8};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 5;
    printf("%d\n", searchInsertPositionOfK(arr1, size1, k1));

    int arr2[] = {1, 3, 5, 6, 7, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 2;
    printf("%d\n", searchInsertPositionOfK(arr2, size2, k2));

    int arr3[] = {1, 3, 5, 6, 7, 8};
    int size3 = sizeof(arr3) / sizeof(arr3[0]);
    int k3 = 9;
    printf("%d\n", searchInsertPositionOfK(arr3, size3, k3));

    return 0;
}


   
/*
run:
 
2
1
6
  
*/

 

70+ SQL courses for beginners and professionals