Finds the place in the given range of specified sorted array, where the element should be inserted for getting sorted array. Uses exponential search algorithm. @param arr - the array with already sorted range @param val - object to be inserted @param l - the start
(Object[] arr, java.lang.Comparable val, int bnd, int l, int r)
| 2809 | * |
| 2810 | */ |
| 2811 | @SuppressWarnings("unchecked") |
| 2812 | private static int find(Object[] arr, java.lang.Comparable val, int bnd, int l, int r) { |
| 2813 | int m = l; |
| 2814 | int d = 1; |
| 2815 | while (m <= r) { |
| 2816 | if (val.compareTo(arr[m]) > bnd) { |
| 2817 | l = m + 1; |
| 2818 | } else { |
| 2819 | r = m - 1; |
| 2820 | break; |
| 2821 | } |
| 2822 | m += d; |
| 2823 | d <<= 1; |
| 2824 | } |
| 2825 | while (l <= r) { |
| 2826 | m = (l + r) >>> 1; |
| 2827 | if (val.compareTo(arr[m]) > bnd) { |
| 2828 | l = m + 1; |
| 2829 | } else { |
| 2830 | r = m - 1; |
| 2831 | } |
| 2832 | } |
| 2833 | return l - 1; |
| 2834 | } |
| 2835 | |
| 2836 | /** |
| 2837 | * Finds the place of specified range of specified sorted array, where the |