moonboat / datastructure / binary serach

分享

   

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

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

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

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>