Page 822 - Introduction to Programming with Java: A Problem Solving Approach
P. 822
788 Appendix 8 Recursion
/*************************************************************
*
BinarySearch.java
Dean & Dean
This uses recursion to find the index of a target value in
an ascending sorted array. If not found, the result is -1.
*************************************************************/
*
*
*
*
public class BinarySearch
{
public static int binarySearch(
int[] arr, int first, int last, int target)
int mid;
int index;
System.out.printf("first=%d, last=%d\n", first, last);
{
if (first == last)
// stopping condition
{
if (arr[first] == target)
{
index = first;
}
}
System.out.println("found");
else Apago PDF Enhancer {
index = -1;
System.out.println("not found");
}
else // continue recursion
{⎫ mid = (last + first) / 2; ⎪
if (target > arr[mid]) ⎪ {⎪
first = mid + 1; ⎪
⎬ }⎪ else ⎪
{⎪ last = mid; ⎪
Do some work.
Then drill down.
}⎭
index = binarySearch(arr, first, last, target); System.out.println("returnedValue=" + index);
}
// end BinarySearch class
}
// end binarySearch
}
return index;
Figure A8.4 Implementation of binary search algorithm
