using System;

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine(SearchInsert(new[]{1}, 1));

        Console.WriteLine(SearchInsert(new[]{1, 3, 5}, 4));

        Console.WriteLine(SearchInsert(new[]{1, 3, 5, 6}, 5));

        Console.WriteLine(SearchInsert(new[]{1, 3, 5, 6}, 2));

        Console.WriteLine(SearchInsert(new[]{1, 3, 5, 6}, 7));

        Console.WriteLine(SearchInsert(new[]{1, 3, 5, 6}, 0));

    }

​

    public static int SearchInsert(int[] nums, int target)

    {

        int r = nums.Length - 1;

        int l = 0;

        while(l <= r){

            var mid = (l + r) / 2;

            if(nums[mid] == target) return mid;

            else if(nums[mid] > target) r = mid-1;

            else l = mid+1;

        }

        return l;

    }

}