If we have sorted arrays we can achieve the same searching speed as from an optimally constructed binary search tree using a recursive search that looks for a specific value somewhere between two array positions:

search(arr[], int lower, int upper, int key)
   if (lower > upper)
      we've run out of positions to search, return false
   else
      midpoint = (lower+upper)/2
      if the midpoint contains the key 
         we've found it, return true
      otherwise if the value in the midpoint is bigger than the key
         then the key must be between positions lower and midpoint-1
         so make a recursive call on that segment
      otherwise the key must be between positions midpoint+1 and upper
         so make a recursive call on that segment

build(arr[], int lower, int upper, tree &t)
   if (lower > upper) we're done (no values left to add)
   otherwise
      midpoint = (lower+upper)/2
      insert arr[midpoint] in the tree
      call recursively on range lower to midpoint - 1
         to get the 'smaller' values inserted in the tree
      call recursively on range midpoint+1 to upper
         to get the 'larger' values inserted in the tree

We can also apply recursive techniques to sort a previously unsorted array.

One such approach uses mergesort, which takes a tree-like approach to dividing the tree into unsorted segments, sorting the smaller segments, and merging them into larger sorted segments:

mergesort(int arr[], int lower, int upper)
   if lower >= upper there is nothing left to sort
   otherwise
      midpoint = (lower+upper)/2
      call mergesort recursively on lower..midpoint
         to get the data in that half of the segment sorted
      call mergesort recursively on midpoint+1..upper
         to get the data in that half of the segment sorted
      merge the two sorted halves into a sorted whole,
         putting the results in positions lower..upper

For a completely different approach to recursive sorting, we can try quicksort:

quicksort(int arr[], int lower, int upper)
   pick a value currently stored in the array segment lower..upper
   put all values smaller than that chosen value
       at one 'end' of the array segment
   put all values larger than that value at the other 'end'
       of the segment
   note the crossover point where the two segments meet
   call quicksort recursively on lower..crossover
       to sort the 'lower end' of the array segment
   call quicksort recursively on crossover+1..upper
       to sort the 'upper end' of the array segment