Is a linear search the best we can do? Well, it turns out that if we are looking at an arbitrary array, this is what we have to do. After all, in an arbitrary array, there is no way to know whether an element is there without potentially looking at all of them. More specifically, we cannot say for sure that some element does not exist, without verifying all the elements. The reason is that the value of one element does not say anything about the values of the other elements.

But, what information can one element have about other elements in an array? One way to make elements have information about the other elements is to have a sorted array instead of just an arbitrary array. What is a sorted array? A sorted array is an array that has all the elements arranged in order of their values. When an array is sorted, every element contains the information that everything on the left is smaller than that particular element, and everything on the right is bigger (or the other way round if the order of the elements is opposite, but we will consider the arrays that are sorted in an increasing order from left to right). This information can, amazingly, make this search a lot faster. Here is what we do:

To avoid creating copies of the array while creating a sub-array, we just pass on the whole array, but we remember the start and end positions we are looking at. The start is included in the range and end is excluded. So, only elements on the right of the start position and the left of the end position are included in the subarray being searched. The following figure gives a visual understanding of binary search:

Figure 1: Binary Search.

An arrow representing moving one element to another during the search.

But, before implementing this algorithm, we need to understand the concept of Comparable. Comparable is an interface in the Java standard library that looks like this:

package java.lang; 
public interface Comparable<T> { 
    public int compareTo(T o); 
} 

Any class implementing this interface has to compare a different object with itself. It is required that the type parameter, T, must be instantiated with the same class that implements it, like this:

public class Integer implements Comparable<Integer>{
    public int compareTo(Integer o){
        …
    } 
}

The compareTo method intends to compare an object of the same type. If the current object (the one that the this reference refers to) is smaller than the object passed, compareTo must return a negative value. If the object passed is smaller, the method must return a positive value. Otherwise, if they are equal, it must return 0. The following conditions are required to be fulfilled by the compareTo method:

Basically, the conditions are the same for a total order where equality is represented by the equals method. It basically generalizes the concept of the < and <= operators, which are there for numbers. Of course, the compareTo method for the Wrapper objects are implemented exactly as the < and <= operators are on the primitives inside them.

Now, we write the search function to do the search, as per the preceding steps:

    private static <E extends Comparable<E>, 
      F extends E> int binarySearch( E[] sortedValues, 
      F valueToSearch, int start, int end) { 
        if(start>=end){ 
            return -1; 
        } 
        int midIndex = (end+start)/2; 
        int comparison = sortedValues[midIndex].compareTo(valueToSearch); 
        if(comparison==0){ 
            return midIndex; 
        }else if(comparison>0){ 
            return binarySearch(sortedValues, valueToSearch, start, midIndex); 
        }else{ 
            return binarySearch(sortedValues, valueToSearch, midIndex+1, end); 
        } 
    }

Note that in this case, we have mandated that the objects in the array must be comparable so that we can know if an object is greater than or less than another object. It does not matter exactly how this relationship is determined; the array must be sorted using the same comparison – that the comparison between two consecutive elements will make sure the element on the left is smaller than the one on the right, as provided by Comparable.

The first if condition checks whether the array passed is empty, if so, obviously the element to be searched is not found and we return -1 to represent this. Then, we find the midIndex and recursively search for the element in either the left or the right subarray. Once we have this function, we create another wrapper function to run the search without having to mention the start and the end positions:

    public static <E extends Comparable<E>, F extends E> int binarySearch( 
            E[] sortedValues, F valueToSearch) { 
        return binarySearch(sortedValues, valueToSearch, 0, sortedValues.length); 
    }

T(n) = T((n-1)/2) + C, where C is a constant.

T(n) = T(n/2) + C

T(2m) = T(2m-1) + C

S(m) = S(m-1) + C

S(m) = mC + D, where D is also a constant.
=> T(2m) = mC + D
=> T(n) = C lg(n) + D

T(n) = O(lg(n))

        int arraySize = 100000000; 
        Long array[] = new Long[arraySize]; 
        array[0] = (long)(Math.random()*100); 
        for(int i=1;i<array.length;i++){ 
            array[i] = array[i-1] + (long)(Math.random()*100); 
        } 

        //let us look for an element using linear and binary search 
        long start = System.currentTimeMillis(); 
        linearSearch(array, 31232L); 
        long linEnd = System.currentTimeMillis(); 
        binarySearch(array, 31232L); 
        long binEnd = System.currentTimeMillis(); 

        System.out.println("linear search time :=" + (linEnd -start)); 
        System.out.println("binary search time :=" + (binEnd -linEnd));