|
public int size() { //hi 高位,lo 低位 int lo = 0, hi = keys.length; while (hi != lo) { int m = (hi+lo)/2; if (keys[m] == null) { h = m; } else { lo = m+1; } return lo; } } /** * Find the index, i, at which x should be inserted into the null-padded * sorted array, a * * @param a * the sorted array (padded with null entries) * @param x * the value to search for * @return i or -i-1 if a[i] equals x */ protected int findIt(T[] a, T x) { int lo = 0, hi = a.length; while (hi != lo) { int m = (hi+lo)/2; int cmp = a[m] == null ? -1 : c.compare(x, a[m]); if (cmp < 0) hi = m; // look in first half else if (cmp > 0) { // look in second half, x always after lo in the right position, and the indicies of children same // with indicies of keys, so plus one will move to the right close child which in the right subtree.
lo = m+1; } else return -m-1; // found it, and can't insert x cause it already exist in B tree node. } return lo; } |
|
|
