In a balanced binary search tree, such as an AVL tree or a red-black tree, the average-case search operation is efficient. The tree's balanced structure ensures that the height remains logarithmic to the number of elements (n), resulting in a time complexity of O(log n) for search operations.