binary serach

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;

}