1.Binary Search
/*
Preconditions: 
   If size>0 , the first through first+size-1 must be valid indexes for the 
array a. Also , starting at a[first] , the next size elements are sorted in 
increasing order form small to large.
*/
public static int search(int[] a , int first , int size , int target)
{
    int middle;
    if(size <= 0)
       return -1;
    else{
       middle = first + size/2;
       if(target == a[middle])
          return search(a, first , size/2 , target);
       else
          return search(a , middle+1 , (size-1)/2 , target);
    }
}
worst-case runningtime: O(logN)
The binary search algorthm is very efficient. For example suppose the constant c is 10. 
Then an array with a thousand elemenets has a running time of 1