Recall from Chapter 11, "Arrays Part II: Multidimensional Arrays. Searching and Sorting Arrays," how we used the binary search technique to locate a number in a sorted array of numbers. The implementation in Chapter 11 made use of iteration. In this section, we will use the same basic ideas of binary search, but this time implemented with a recursive method. Because the underlying ideas are the same whether we use iteration or recursion, you might want to revisit the binary search section in Chapter 11 before beginning the recursion example described next.

The binary search technique can be viewed as a series of searches where each search is a smaller version of the previous search. Each search can briefly be described as follows. First, find the middle element of the part of the array we are searching and then compare this element with the search key (the number for which we are looking to find a match). If they match, we are done. The middle element's index then contains a value that matches the search key, so this index value is returned (this is the base case). Otherwise, if the search key is less than the middle element value, search in the sub-array (this is a smaller version of the previous search) that is situated to the left of the middle element. Otherwise, if the search key is greater than the middle element, search in the sub-array (this is also a smaller version of the previous search) that is situated to the right of the middle element. If at any point we are searching an empty array, the search key does not exist anywhere in the entire array.

Notice how we can define the binary search in terms of smaller versions of itself and a base case. Listing 23.5 contains the recursive method `BinarySearch` in lines 13 28 that implements the presented logic.

01: using System; 02: 03: class Searcher 04: { 05: private static int[] arr; 06: 07: public static int StartSearch(int[] newArray, int searchKey, int low, int high) 08: { 09: arr = newArray; 10: return BinarySearch(searchKey, low, high); 11: } 12: 13: public static int BinarySearch(int key, int low, int high) 14: { 15: if(low > high) 16: return -1; 17: else 18: { 19: int mid = (low + high) / 2; 20: 21: if(key == arr[mid]) 22: return mid; 23: else if (key < arr[mid]) 24: return BinarySearch(key, low, mid - 1); 25: else 26: return BinarySearch(key, mid + 1, high); 27: } 28: } 29: } 30: 31: class Tester 32: { 33: public static void Main() 34: { 35: int searchKey; 36: int searchResult; 37: int[] testScores = { 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32, 34,36,38} ; 38: 39: do 40: { 41: Console.Write("Please enter the test score you would like to locate: "); 42: searchKey = Convert.ToInt32(Console.ReadLine()); 43: searchResult = Searcher.StartSearch(testScores, searchKey, 0, 18); 44: if(searchResult >= 0) 45: Console.WriteLine("The score was found in position: { 0}\ n", searchResult); 46: else 47: Console.WriteLine("The score was not found\ n"); 48: Console.Write("Would you like to do another search? Y)es N)o "); 49: } while (Console.ReadLine().ToUpper() == "Y"); 50: } 51: } Please enter the test score you would like to locate: 4<enter> The score was found in position: 1 Would you like to do another search? Y)es N)o Y<enter> Please enter the test score you would like to locate: 11<enter> The score was not found Would you like to do another search? Y)es N)o Y<enter> Please enter the test score you would like to locate: 38<enter> The score was found in position: 18 Would you like to do another search? Y)es N)o N<enter>

The array we are searching must be sorted for the binary search to work correctly. In this case, we are searching the array `testScores` declared in line 37 that, via the `StartSearch` method (called in line 43), is assigned (in line 9) to the `arr` array (declared in line 5).

The recursive `BinarySearch` method contains the classic elements of a recursive method `if-else` statements (lines 15 27 and lines 21 26) with two base cases (line 16 and 22) and two recursive calls (lines 24 and 26).

The `key` parameter (declared in line 13) contains the value we are searching for, while the parameters `low` and `high` represent the index values (not the score values themselves) that enclose the part of the `arr` array we are searching. `BinarySearch`'s return value (of type `int`) contains the index of the `arr` array where an element value matching that of `key` was located; if a match to `key` is not found, `-1` is returned.

For a moment, let's concentrate on lines 19 26 that are processed as long as there is still a part of the array we haven't searched.

First, the middle index (represented by `mid`) of the `arr` array we are searching is determined (line 19). Line 21 then checks if `key` is located in this middle element. If this is the case, this index value is returned to the caller in line 22. If not, we must continue our search either in line 24 or line 26. If `key` is less than the middle element (checked in line 21), the `key` value for which we are searching must be located between the `low` index and the `(mid`-`1)` index. Consequently, we ask `BinarySearch` to search this part of the `arr` array by invoking it with these arguments in line 24.

Observe that the `low` argument is assigned to the `BinarySearch`'s `low` parameter, and the `mid`-`1` argument is assigned to `BinarySearch`'s `high` parameter. With this call, we have eliminated half or so of the array part we need to search, and is, consequently, moving towards a base case.

If `key` is greater than the middle element, it makes sense instead to search the part of the array located between index `mid + 1` and `high`, as reflected in the call to `BinarySearch` in line 26. Notice that with both the calls to `BinarySearch`, we simply take for granted that `BinarySearch` performs its job correctly of locating an index with the matching element. If an element does exist with a value that matches that of `key`, we are moving toward the base case in lines 21 and 22 with every recursive call. However, if no element value matches that of `key`, an infinite number (was it not for lines 15 and 16) of recursive calls will occur. To realize why lines 15 and 16 properly detect that the key value cannot be found and that they effectively prevent an infinite number of recursive calls to take place, consider the following logic. In each recursive call, either the value of `low` is increased or the value of `high` is decreased. If `low` ever becomes greater than `high`, it means that there are no elements left to check in the array and that the `key` value did not exist in `arr`. Thus, according to our convention from earlier, `-1` is returned to the caller in line 16.

Note

To see an example where recursion is used to convert numbers between different number systems, please consult Appendix D, "Number Systems," located on this book's Web site at www.samspublishing.com. |

C Primer Plus (5th Edition)

ISBN: 0672326965

EAN: 2147483647

EAN: 2147483647

Year: 2000

Pages: 286

Pages: 286

Authors: Stephen Prata

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net