[plt-scheme] htdp exercise 12.2.2

On Jun 3, 2009, at 3:08 PM, aditya shukla wrote:

> The exercise 12.2.2 illustrates the concept of search and then asks  
> to implement search-sorted.It says that search-sorted takes the  
> advantage that the list is sorted. My question is then what's the  
> difference between search and search-sorted. Because  for both we  
> can check for the first and do recursion on the rest of the list?

What does "take advantage of" mean?
Since the original search function works on ANY list, it will  
obviously still work on a sorted list.  The "search-sorted" function  
therefore can't be any more CORRECT than the original function, so it  
must be better in some other way, like speed.  How could you use the  
assumption that the list is sorted to make the function run faster?

(There's a simple way that makes the function slightly faster, and  
another way that makes the function much faster but requires a  
different data structure instead of a list.  I assume HtDP expects  
the former....)



Stephen Bloch
sbloch at adelphi.edu