Question

How to find the index of N in a sorted vector if N is not present, return the index where it would be in C

Answer 1

#include <stdio.h>

// Function to find the index where N would be inserted
int findInsertPosition(const int arr[], int size, int N) {
    int left = 0;
    int right = size;

    // Binary search to find the lower bound
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < N)
            left = mid + 1;
        else
            right = mid;
    }

    return left; // Return the index
}

int main() {
    // Sorted array
    int arr[] = {1, 3, 5, 7, 8, 9, 12, 15};
    int size = sizeof(arr) / sizeof(arr[0]);

    int N = 6; // Element to find or insert

    int index = findInsertPosition(arr, size, N);

    printf("Index where %d is OR would be: %d\n", N, index);

    return 0;
}


/*
run:

Index where 6 is OR would be: 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>

// Function to find the index and check existence
void findOrInsertPosition(const int arr[], int size, int N) {
    int left = 0;
    int right = size;

    // Binary search to find the lower bound
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < N)
            left = mid + 1;
        else
            right = mid;
    }

    int index = left; // Index where N would be inserted

    // Check if N exists at that index
    if (index < size && arr[index] == N)
        printf("Found at index: %d\n", index);
    else
        printf("Index where %d would be: %d\n", N, index);
}

int main() {
    // Sorted array
    int arr[] = {1, 3, 5, 7, 8, 9, 12, 15};
    int size = sizeof(arr) / sizeof(arr[0]);

    int N = 6; // Element to find or insert

    findOrInsertPosition(arr, size, N);    
    findOrInsertPosition(arr, size, 9);

    return 0;
}


/*
run:

Index where 6 would be: 3
Found at index: 5

*/

 

70+ SQL courses for beginners and professionals