バイナリ検索ツリーはどこから始めるのですか？

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)