1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
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,
25: // anArray[first] <= target <= anArray[last]
26: int mid = first + (last - first) / 2;
27: if (target == anArray[mid])
28: index = mid; // target found at anArray[mid]
29: else if (target < anArray[mid])
30: // Point X
31: index = binarySearch(anArray, first, mid - 1, target);
32: else
33: // Point Y
34: index = binarySearch(anArray, mid + 1, last, target);
35: } // end if
36:
37: return index;
38: } // end binarySearch