Binary Search Using Recursion

   


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.

Listing 23.5 RecursiveBinarySearch.cs
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",  graphics/ccc.gifsearchResult); 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

graphics/common.gif

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
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2000
Pages: 286
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net