Java Reference
In-Depth Information
13582050100
If we are searching for the integer 5, we can apply the same approach as the guessing
game. We can first examine the element in the middle: 8. Since 5 is smaller than 8 and the
array is sorted, then it must be the case that the number 5 is in the first part of the array.
We can then shrink the search interval to the first half of the array and apply the algorithm
recursively. The base case will be when we have an array of a single element. Then we can
immediately tell if the number is in the array or not. If the number is not in the array, then
we will return
1. Otherwise, we will return the index of the number we are searching for
in the array. A possible implementation follows.
class BinarySearch {
public static void main(String [] args)
{
{
}
int [] a =
;
System. out . println(binarySearch(0 , a. length
1,3,5,8,20,50,100
1, 5, a)) ;
}
public static int binarySearch( int start , int end ,
int number ,
int []
a) {
int mid = (start + end) / 2;
if (start == end) {
if (a [ end ] == number)
{
return end ;
}
else {
return 1;
}
if (a[mid] > = number) {
return binarySearch(start , mid, number, a) ;
return binarySearch(mid + 1, end , number,a) ;
}
}
Note that every time the binarySearch method is called, a different part of the array
needs to be passed as a parameter. Since creating a new array from an existing array is
not a trivial task, we have chosen to pass the start and end index of the new array as
parameters. Note that the array is also passed as a parameter. Since the value of the array
reference is not changed, we can think of it as a constant that the binarySearch method
needs to access, but never change. Such constants are common in recursive methods. As an
alternative, the a array could have been defined as a global variable. However, this is an
inferior solution because the array will now be accessible by all the methods in the class.
The base case is when the array has a single element. If it is our integer, then we
return the index of the element. Otherwise, the method returns
1. In the general case,
we recursively search in the first or the second half of the array depending on whether the
search number is smaller or bigger than the middle of the array, respectively. It is interesting
to note that the running time of the method is logarithmic. For example, we can find the
element that we are looking for in an array of one million elements using at most 20 recursive
calls.
Note that the binary search code uses tail recursion. Recursive calls are always at the
end of the execution paths and there is at most one recursive call at the end of every path.
Therefore, the code can be rewritten to use an infinite while loop as follows.
public static int binarySearch( int start , int end ,
int number ,
int [] a) {

Search WWH ::

Custom Search