[Search][Binary search] Search Insert Position

1. Example

[1,3,5,6], insert 5 at index 2
[1,3,5,6], insert 2 at index 1
[1,3,5,6], insert 7 at index 4
[1,3,5,6], insert 0 at index 0


2. Implementation
Thought 1: find out two adjacent number which are most close left bound and right bound for the target value.
Q1: how to find these two number
A1: try to find a number first, we can redefine this question like find the target value
Q1: any best way to find a target value?
A1: Binary search  will do the job just right
Q1: BS criterion?
A1: sorted array
Last executed input: [1], 0 if r != m-1 Last executed input: [1], 2 if l != m+1
NOTE: 
while ( l <= r )
 else if ( nums[m] > target )
 {
 r = m-1;
 }
 else
 {
 l=m+1;
 }

// Time :O(log(n)), Space:O(1)
public int searchInsert(int[] nums , int target)
{


     // valid the input
     if (nums == null || nums.length == 0)
     {
         return 0; // first element
     }




     int l = 0;
     int r = nums.length-1;
     // NOTE: when l increment to length-1 (==r) and the value there still less than target, left increment to length and (1 > r) return 
     // NOTE: when r change to 0 (==l) and the value there still larger than target, r change to -1(l>r) and return left
     while (  l <= r  )
     {
           int m = l + (r-l)>>1;
           if ( nums[m] == target )
           {
                return m;
           }
           else if ( nums[m] > target )
           {
                // NOTE:  for the case [1], 0, if r= m instead of m-1 then m always 0 and l always 0, infinite loop
                //r = m;
                r = m-1;
           }
           else 
           {
                l=m+1;
           }
     }
     return l;



}

3. Similar Ones
(M) Search for a range
       Search a 2D matrix