從哪裏開始使用二叉搜索樹？

Question

按照我的理解，當你完成一個二分查找時，你從中間值開始，在它上面完成一個分而治之的算法，直到找到正確的值。

但是，當我查看二叉搜索樹時，我的理解是，這是以相同的方式完成的，初始節點是中間值，但是我看到了以第一個節點爲第一個值開始的未排序列表示例在數組中。

哪種方法是正確的？

謝謝

Answer 1

通常，您從中間節點開始，然後檢查左右兩半。

劃分和征服算法通過將原始問題分解爲更小尺寸的子問題來遞歸地解決問題。這個問題將會減少，直到它足夠小，以直接的方式解決。

它是二叉搜索樹的情況下，算法採取中間節點，然後遞歸解決右側和左側的子問題。

BinarySearch(Array arr, value) 
    return BinarySearchAux(arr, value, 0, arr.length) 

BinarySearch(Array arr, value, start, end) 
    if start >= end 
     return value == arr[start] 
    mid = floor((end - start)/2) 
    if value == arr[mid] 
     return true 
    return 
     BinarySearchAux(arr, value, start, mid-1) || 
     BinarySearchAux(arr, value, mid+1, end)