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)
{
