Algorithms For Dummies

 

   

  PART 1 

 Getting Started

Note that this example makes one of two recursive calls. When 

key

 is greater than 

the midpoint value of the existing list, 

searchList[mid]

, the code calls 

search

 

again with just the right side of the remaining list. In other words, every call to 

search

 uses just half the list found in the previous call. When 

key

 is less than or 

equal to 

searchList[mid]

, search receives the left half of the existing list.

The list may not contain a search value, so you must always provide an escape 

method for the recursion or the stack will fill, resulting in an error message. In 

this case, the escape occurs when 

mid == 0

, which means that there is no more 

searchList

  to  search.  For  example,  if  you  change 

search(aList, 5)

  to 

search(aList, 22)

, you obtain the following output instead:

Searching midpoint at  11

searchList now contains  [11, 12, 13, 14, 15, 16, 17, 18,

 19, 20]

Searching midpoint at  16

searchList now contains  [16, 17, 18, 19, 20]

Searching midpoint at  18

searchList now contains  [18, 19, 20]

Searching midpoint at  19

searchList now contains  [19, 20]

Searching midpoint at  20

searchList now contains  [20]

Searching midpoint at  20

Key Not Found!

Note also that the code looks for the escape condition before performing any other 

work to ensure that the code doesn’t inadvertently cause an error because of the 

lack of 

searchList

 content. When working with recursion, you must remain pro-

active or endure the consequences later.