Lower_bound function
public static int lower_bound ( int [ ] arr , int key ) { int low = 0 ; int high = arr . Length - 1 ; while ( low < high ) { int mid = low + ( high - low ) / 2 ; if ( arr [ mid ] >= key ) { high = mid ; } else { low = mid + 1 ; } } return low ; }