Arrays - A Concise and Practical Introduction to Programming Algorithms in Java - page 100

also called the linear search since it takes time proportional to the array length.
The algorithmic question raised is to know whether there exists or not a faster
method? Observe that in the above program the array elements were ordered in
increasing order. We should try to use this extra property to speed-up the search
algorithm. The idea is to skip browsing some portions of the arrays for which
we know that the query element cannot be found for sure. Start with a search
interval [ left , right ] initialized with the extremal array indices: left =0and
right = n

1 where n denote the array length array.length .Let m denote the
index of the middle element of this range: m = (left + right) / 2. Then execute
recursively the following steps:

−

- If array[m]==E then we are done, and we return index m ,
- If array[m] <E , then if the element is inside the array, it is necessarily within
range [ m +1 , right],

- If array[m] >E , then if the element is inside the array, it is necessarily within
range [left ,m + 1].

The search algorithm terminates whenever we find the element, or if at some
point left>right . In that latter case, we return index

1 for reporting that we
did not find the query element. Thus the dichotomic search (also called binary
search) is a provably fast method for searching whether or not a query element
is inside a sorted array by successively halving the index range. The number of
steps required to answer an element membership is thus proportional to log 2 n .
The dichotomic search is said to have logarithmic time complexity . These time
complexity notions will be further explained in Chapter 6. We summarize the
bisection search by the following code:

−

Program 4.16 Binary search: Fast dichotomic search on sorted arrays
class BinarySearch {
static int Dichotomy( int [ ] array , int left , int right , int

key)
if (left > right)
return − 1;
int m=(left+right )/2;
if (array [m]==key)
{ return m; }
else
if (array [m] < key) return Dichotomy( array ,m+1, right , key ) ;
else return Dichotomy( array , left ,m − 1, key) ;

}
static int DichotomicSearch( int [ ] array , int key)
{ return Dichotomy( array ,0 , array . length

− }

1, key) ;

public static void main ( String [ ] args )