Esempio, la binary search puรฒ essere anche implementata in modo ricorsivo:
/**
* Search in the array A in positions numbered loIndex to hiIndex, inclusive,
* for the specified value. If the value is found, return the index in the array
* where it occurs. If the value is not found, return -1. Precondition: The
* array must be sorted into increasing order.
*/
static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {
if (loIndex > hiIndex) {
// The starting position comes after the final index,
// so there are actually no elements in the specified
// range. The value does not occur in this empty list!
return -1;
} else {
// Look at the middle position in the list. If the
// value occurs at that position, return that position.
// Otherwise, search recursively in either the first
// half or the second half of the list.
int middle = (loIndex + hiIndex) / 2;
if (value == A[middle])
return middle;
else if (value < A[middle])
return binarySearch(A, loIndex, middle - 1, value);
else // value must be > A[middle]
return binarySearch(A, middle + 1, hiIndex, value);
}
} // end binarySearch()
Linked data structures
Struttura dati definita in modo ricorsivo:
class Node {
String item;
Node next;
}
Alberi binari
class TreeNode {
int item; // The data in this node.
TreeNode left; // Pointer to the left subtree.
TreeNode right; // Pointer to the right subtree.
}
