分享

更多

   

binary serach

2015-01-13  moonboat



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;
}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章
    喜欢该文的人也喜欢 更多