Quanto tempo funciona a árvore de pesquisa?

O tempo de busca numa árvore depende do tipo de árvore e da operação. Para árvores binárias de busca balanceadas (por exemplo, AVL, árvore vermelho-preto), a busca, inserção e remoção operam em O(log n), onde n é o número de elementos. No pior caso, para uma árvore binária não balanceada, a busca pode degradar para O(n). Por exemplo, em Go, pode-se implementar uma busca binária num slice ordenado em O(log n):

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // não encontrado
}