Time complexity : O(log(n))
we are simply using binary search algorithm here to search the ceiling index , because there only we will insert the incoming value .
ceiling value : its either equal to the target element , or the smallest value among the elements which r larger than target .
Example :
array = { 1 , 2 , 3 ,4 , 5 , 8 ,9 }
target = 5 , ceiling value = 5
target = 6 , ceiling value = 8
so if 6 is coming , it will take index of 8 only ,
Hope I was able to make you unserstand :)

class Solution
{
public int searchInsert(int[] nums, int target)
{
int start = 0;
int end = nums.length -1;
while(start <= end)
{
int mid = start + (end - start )/2;
if(nums[mid] == target )
return mid;
else if(nums[mid] < target)
start = mid+1;
else
end = end-1;
}
return start ;
}
}
Try it once on paper , to understand it better :) ,
int mid = start + (end - start )/2;
is equal to int mid = (start + end )/2;
its a better approach to prevent integer overflow .

If something confuses u , feel free to ask me the same