Searching and Sorting - A Concise and Practical Introduction to Programming Algorithms in Java - page 133

- We cannot remove inserted Person objects. The array data-structure is semi-
dynamic.

Furthermore, note that in practice we need to check if a person already belongs
to the array before eventually adding his/her records.

6.3.3 Dichotomy/bisection search

The dichotomy search is also called bisection search. The method was sketched
in chapter 4.7. To perform a bisection search, we need to have an array fully
sorted with respect to the object keys. The bisection search proceeds as follows:
Start with a search interval [ left , right ] initialized with 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 the
following recursive steps:

−

- If array[m]=E then we are done, and we return the index position m,

- If array[m] <E , then if the solution exists it is necessarily within range
[ m +1 , right],

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

The search algorithm terminates whenever left>right .Inthatcase,we
return index

1 for signaling that we did not find the quey element. Thus
a dichotomic search (also called binary or bisection search) is a fast method for
searching whether a query element is inside a sorted array or not 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 complexity.
The bisection search code is as follows:

−

Program 6.5 Bisection search on sorted arrays
static int Dichotomy( int [ ] array , int left , int right , int

key)
{ if (left > right) return − 1;

int m=(left+right)/2; // !!! Euclidean division !!!

if (array [m]==key) return m;
else
if (array [m] < key) return Dichotomy( array ,m+1, right , key )
;