0 0        binary serach

2015-01-13
 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; }

0条评论