引入一個例題來說明折半查找二叉樹與平衡二叉樹的差別：
已知一個長度為16的順序表，其元素按關鍵字有序排列，若采用折半查找算法查找一個不存在的元素，則比較的次數至少和至多的情況分别是：
首先，需要知道如何建構一棵折半查找二叉樹，因為折半查找要求元素需以有序的順序表形式進行存儲，假設這16個數就是1~16構成的有序序列，構造的折半查找二叉樹如下：
右圖為将其所有的失敗情況進行補充，我們發現，折半查找二叉樹是一棵平衡的二叉排序樹，要查找一個元素，其查找長度（即關鍵字對比次數）不會超過樹的高度，而對于一棵具有平衡二叉樹性質的二叉樹，其樹高h=log2(n+1)向上取整，是以，折半查找的時間複雜度不會超過O(log2n)
如果是二叉排序樹，該案例的情況是一棵單枝樹，此時查找失敗的查找長度為O(n)，n為數高，同時也為節點的個數，這是由于，二叉排序樹的建樹取決于初始節點是否有序，有序的情況下會形成單枝樹，此時查找的性能最差，同時，二叉排序樹最好的時間性能同折半查找二叉樹，為O(log2n)
回到本題，對于折半查找失敗的情況就一目了然了，最好的對比次數為4，最多的對比次數為5，才可以判定查找失敗