注:该版代码会满江紫,请不要提交到任何一道二分题上
如果要在一个区间内查找一个数,我们一般会使用二分。
二分的思想简单,实现容易,时间复杂度也只有O(logN),几乎是没有缺点的一个查找方式。
燃鹅,有一种数据结构叫做树...
昨天,我突发奇想,能不能利用堆向下调整的思想,进行查找?
于是,实践开始!
我们先弄一棵树,啊不,堆:
1
/ \
2 3
/ \ / \
4 5 6 7
我们假设要查4的位置:
我们先从根节点开始查:
1不行,2与3也不行...
这个时候,我们先往左子树搜;
于是就变成了2 4 5。
再搜一遍,发现:左儿子是4!好了,任务完成。
but
如果要搜7,那就完了:
左子树没有,返回-1(此处默认没找到返回-1),那怎么办?搜右子树!
好在这棵树比较浅,3 6 7,右儿子就是7,因此任务成功完成。
整个堆查找的时间复杂度是不稳定的,最好O(logN),最坏O(N),非常之难用......
本人最近正在寻找解决方案,如果您有思路/疑问,请在帖子的下方留言评论,我会根据您的评论改进堆查找。
int heapfind(int num,int find)
{
if (num>节点总数) return -1;//越界返回-1
else if(heap[num]==find) return num;//自己
else if(heap[num+1]==find) return num+1;//兄弟
else if(heap[num<<1]==find) return num<<1;//左儿子
else if(heap[num<<1|1]==find) return num<<1|1;//右儿子
else{
return max(heapfind(num<<1,find),heapfind(num<<1|1.find));
}