1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: /** Searches the array anArray[first] through anArray[last]
5: for a given value by using a binary search.
6: @pre 0 <= first, last <= SIZE - 1, where SIZE is the
7: maximum size of the array, and anArray[first] <=
8: anArray[first + 1] <= ... <= anArray[last].
9: @post anArray is unchanged and either anArray[index] contains
10: the given value or index == -1.
11: @param anArray The array to search.
12: @param first The low index to start searching from.
13: @param last The high index to stop searching at.
14: @param target The search key.
15: @return Either index, such that anArray[index] == target, or -1.
16: */
17: int binarySearch(const int anArray[], int first, int last, int target)
18: {
19: int index;
20: if (first > last)
21: index = -1; // target not in original array
22: else
23: {
24: // If target is in anArray, anArray[first] <= target <= anArray[last]
25: int mid = first + (last - first) / 2;
26: if (target == anArray[mid])
27: index = mid; // target found at anArray[mid]
28: else if (target < anArray[mid])
29: // Point X
30: index = binarySearch(anArray, first, mid - 1, target);
31: else
32: // Point Y
33: index = binarySearch(anArray, mid + 1, last, target);
34: } // end if
35:
36: return index;
37: } // end binarySearch