Java Reference
In-Depth Information
14.4 Array Algorithms
Next, we show five sorting algorithms and one algorithm that finds a number in a sorted
array. Many of the problems can be easily solved without using recursion. However, in order
to demonstrate how to use recursion on algorithms with arrays, we will present a recursive
solution for each of the problems. Where applicable, we will also show the non-recursive
solution.
14.4.1 Binary Search
It is time to write another game. We will ask the player to think of a number between
1 and 1000. Then our program will be able to guess the number in 10 tries or less. Every
time the user just needs to tell the program if their number is higher, lower, or equal to the
computer guess. At every step, the computer is given an interval (originally [1,1000]). The
computer's guess is always in the middle of the interval. Based on the user response, the
computer will keep shrinking the interval. For example, the computer will first guess 500.
If the user says higher, then the computer will examine the interval [501,1000] and apply
the same algorithm. The base case is when the interval consists of a single number (it must
be the user's number) or when the user admits that we have guessed the number. Here is a
possible implementation.
import
java . util .
∗
;
public class
GuessingGame
{
public static void
main(String [] args)
{
System. out . println (
"Please think of a number between 1 and 1000"
);
guess(1,1000, 500) ;
}
public static void
guess(
int
low ,
int
high ,
int
guess)
{
if
(low == high)
{
System. out . println (
"Your number must be: "
+low ) ;
System. exit(0) ;
System. out . print (
"Is your number higher(h), lower(l), or equal(e)
to: "
+guess+
": "
);
Scanner keyboard =
new
Scanner(System. in) ;
String result = keyboard.next() ;
switch
( result . charAt (0) )
{
case
:
guess(guess+1,high , (guess+high+1)/2) ;
break
;
case
'h'
:
guess(low, guess
−
1, (low+guess
−
1)/2) ;
break
;
case
'e'
:
System. out . println (
"I win again!"
);
System. exit(0) ;
'l'
}
}
}
Here is one possible run of the program (user input in italic):
Please think of a number between 1 and 1000
Is your number higher(h), lower(l), or equal(e) to: 500:
h
