// By using tasks explcitly.
    public static void DoTree<T>(Tree<T> tree, Action<T> action)
    {
        if (tree == null) return;
        var left = Task.Factory.StartNew(() => DoTree(tree.Left, action));
        var right = Task.Factory.StartNew(() => DoTree(tree.Right, action));
        action(tree.Data);

        try
        {
            Task.WaitAll(left, right);
        }
        catch (AggregateException )
        {
            //handle exceptions here
        }
    }

You can easily use parallelism.

For k is less than n processors, split the array into n/k groups and assign a processor to each group.

Run binary search on that group.

Now the time is log(n/k).

There is also a crew method that is logn/log(k+1).