[Python] Recursive algorithm from tonight

[Trent Robbins]

Nice post!

For anyone following along at home, the code we sent out last night should
come with the caveat that it was programmed by the class as a learning
project, this isn't an 'efficient algorithm', it's some practice trying to
achieve a programming goal.

It was pretty educational because on the one hand we found our target
number using a recursive search, but on the other hand we missed our goal
of getting the INDEX of the value due to our architectural decisions.  This
pitfall is really interesting!


Greg -

For a more standard treatment of Binary Search Trees this website seems
pretty good: http://cslibrary.stanford.edu/110/BinaryTrees.html

Note how they use pointers instead of slicing the list and creating a new
list for each recursive call.

Pointers are a very popular concept for algorithms, so I definitely
recommend this. It will also solve our problem of trying to know the index
of the value we find without resorting to the "if number in list" pattern.
The pattern is pretty clever, but on the other hand it uses Python's built
in __contains__ for an iterator. I haven't read a great deal about
this but here
is the Python Reference for __contains__
<https://docs.python.org/2/reference/datamodel.html#object.__contains__>.







Best,

Trent Robbins
Tau Informatics LLC
desk: 415-404-9452
cell: 513-233-5651
trent at tauinformatics.com
@trentrobbins

On Tue, May 10, 2016 at 1:51 PM, Greg Gorlen <gsgorlen at gmail.com> wrote:

> Thanks for the lively discussion!  As we wrapped up class, it seems we
> discussed at least two ways to return the index rather than the value or a
> T/F:
>
> 1) Keep the slicing approach and store the original list as a variable
> which can be looked at after we find a match to see what the original index
> was.
> 2) Don't slice the list and keep passing the original list through the
> method call but update boundary search indexes as we go, looking at smaller
> pieces of the same list.
>
> Personally, I prefer the second method from a performance standpoint,
> since we aren't making new lists (as far as I can tell), and since the
> first method may as well just trim the search off and keep the index check:
>
> if number in list: print list.index(number)
> else: print False
>
> so I tried to implement option #2 from the class version (see attached,
> Py3).  Of course, we could still just do the above, but that's too easy!
>
> As for Evan's idea about returning all indexes where the search term
> exists... We could create a second method, find_adjacent_values(sorted_list,
> target_value), which is called if we find a match in our bst.  This
> method creates a list to store any return value(s), then checks each value
> adjacent to our target in either direction, appends any such values to the
> list or increments a total count, then ends when it finds an inequivalent
> value in either direction and returns its list or total count.
>
> This is my first post to the list so I hope the attachment and so on works
> OK.  Apologies if not.
>
> Best,
> Greg
>
>
> On Mon, May 9, 2016 at 9:13 PM, Trent Robbins <robbintt at gmail.com> wrote:
>
>> Hi All,
>>
>> Attached is our implementation of the binary search tree.
>>
>> We got the value of the result, if you would like to try getting the
>> index of the result, please refer to the course notes for a sample of the
>> search algorithm.
>>
>> Trent
>>
>> _______________________________________________
>> Python mailing list
>> Python at lists.noisebridge.net
>> http://www.noisebridge.net/mailman/listinfo/python
>>
>>
>
> _______________________________________________
> Python mailing list
> Python at lists.noisebridge.net
> http://www.noisebridge.net/mailman/listinfo/python
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.noisebridge.net/pipermail/python/attachments/20160510/01a8141f/attachment-0003.html>