Question

How to search insert position of K in a sorted list with C#

Answer 1

// Given a sorted array/vector/list 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.

using System;
using System.Collections.Generic;

class Program
{
    // Function to find the index of k or the position where it should be inserted
    static int SearchInsertPositionOfK(List<int> list, int k) {
        for (int i = 0; i < list.Count; i++) {
            // If k is found or needs to be inserted before list[i]
            if (list[i] >= k) {
                return i;
            }
        }

        // If k is greater than all elements, it should be inserted at the end
        return list.Count;
    }

    static void Main()
    {
        List<int> list1 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k1 = 5;
        Console.WriteLine(SearchInsertPositionOfK(list1, k1));

        List<int> list2 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k2 = 2;
        Console.WriteLine(SearchInsertPositionOfK(list2, k2));

        List<int> list3 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k3 = 9;
        Console.WriteLine(SearchInsertPositionOfK(list3, k3));
    }
}



/*
run:

2
1
6

*/

 

Learn SQL from A to Z at LearnSQL.com

Answer 2

// Given a sorted array/vector/list 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.

using System;
using System.Collections.Generic;

class Program
{
    // Function to find the index of k or the position where it should be inserted - Using Binary Search
    static int SearchInsertPositionOfK(List<int> list, int k)
    {
        int left = 0, right = list.Count - 1;

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

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

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

    static void Main()
    {
        List<int> list1 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k1 = 5;
        Console.WriteLine(SearchInsertPositionOfK(list1, k1));

        List<int> list2 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k2 = 2;
        Console.WriteLine(SearchInsertPositionOfK(list2, k2));

        List<int> list3 = new List<int> { 1, 3, 5, 6, 7, 8 };
        int k3 = 9;
        Console.WriteLine(SearchInsertPositionOfK(list3, k3));
    }
}



/*
run:

2
1
6

*/

 

Learn SQL from A to Z at LearnSQL.com