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, Comparable val, int bnd, int l, int r)
| 2572 | * |
| 2573 | */ |
| 2574 | @SuppressWarnings("unchecked") |
| 2575 | private static int find(Object[] arr, Comparable val, int bnd, int l, int r) { |
| 2576 | int m = l; |
| 2577 | int d = 1; |
| 2578 | while (m <= r) { |
| 2579 | if (val.compareTo(arr[m]) > bnd) { |
| 2580 | l = m + 1; |
| 2581 | } else { |
| 2582 | r = m - 1; |
| 2583 | break; |
| 2584 | } |
| 2585 | m += d; |
| 2586 | d <<= 1; |
| 2587 | } |
| 2588 | while (l <= r) { |
| 2589 | m = (l + r) >>> 1; |
| 2590 | if (val.compareTo(arr[m]) > bnd) { |
| 2591 | l = m + 1; |
| 2592 | } else { |
| 2593 | r = m - 1; |
| 2594 | } |
| 2595 | } |
| 2596 | return l - 1; |
| 2597 | } |
| 2598 | |
| 2599 | /** |
| 2600 | * Finds the place of specified range of specified sorted array, where the |