Search Insert Position
The core tech of InsertionSort
a InsertionSort is like
sorted is an array to store sorted values
foreach value in input
p = search_insert_position(sorted_array, value)
insert value at p in the sorted_array
Where to insert
The sorted array is in non-descending order. The first A[i] greater than or equals to the value is where to insert the value.
Source code Read on Github
1 public class Solution {
2 public int searchInsert(int[] A, int target) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4 for(int i = 0; i < A.length; i++){
5 if(A[i] >= target) return i;
6 }
7 return A.length;
8 }
9 }