版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明
刚有人问我一个题扯到了折半查找法,于是我做了下发现有两种方法可以实现。
茬有序表中把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现:
2) 待查找数据值比中间元素值小则以整个查找范圍的前半部分作为新的查找范围,执行1)直到找到相等的值。
3) 待查找数据值比中间元素值大则以整个查找范围的后半部分作为新的查找范围,执行1)直到找到相等的值
按照二叉树来理解:中间值为二叉树的根,前半部分为左子树后半部分为右子树。折半查找法的查找次数正好为该值所在的层数等概率情况下,约为