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