<div dir="ltr">Nice post!<div><br></div><div>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.</div><div><br></div><div>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!</div><div><br></div><div><br></div><div>Greg -</div><div><br></div><div>For a more standard treatment of Binary Search Trees this website seems pretty good: <a href="http://cslibrary.stanford.edu/110/BinaryTrees.html">http://cslibrary.stanford.edu/110/BinaryTrees.html</a></div><div><br></div><div>Note how they use pointers instead of slicing the list and creating a new list for each recursive call.</div><div><br></div><div>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 <a href="https://docs.python.org/2/reference/datamodel.html#object.__contains__">here is the Python Reference for __contains__</a>.</div><div><br></div><div><br></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div style="font-family:arial;font-size:small"><div><br></div><div><br></div><div><br></div><div><br></div><div>Best,</div><div><br></div><div>Trent Robbins</div><div>Tau Informatics LLC</div><div>desk: 415-404-9452</div><div>cell: 513-233-5651</div><div><a href="mailto:trent@tauinformatics.com" target="_blank">trent@tauinformatics.com</a></div><div>@trentrobbins</div></div></div></div></div></div></div></div></div>
<br><div class="gmail_quote">On Tue, May 10, 2016 at 1:51 PM, Greg Gorlen <span dir="ltr"><<a href="mailto:gsgorlen@gmail.com" target="_blank">gsgorlen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div>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:<br></div><br>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.<br></div>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.<br></div><br>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:<br><span style="font-family:monospace,monospace"><br>if number in list: print<span> list</span><span>.</span><span>index</span><span>(number</span><span>)</span><br>else: print False<br></span><br></div><div>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!<br><br></div><div>As for Evan's idea about returning all indexes where the search term exists... We could create a second method, <span style="font-family:monospace,monospace">find_adjacent_values(sorted_list, target_value)</span>, 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.<br><br></div><div>This is my first post to the list so I hope the attachment and so on works OK. Apologies if not.<br></div><div><br>Best,<br></div>Greg<br><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On Mon, May 9, 2016 at 9:13 PM, Trent Robbins <span dir="ltr"><<a href="mailto:robbintt@gmail.com" target="_blank">robbintt@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr">Hi All,<div><br></div><div>Attached is our implementation of the binary search tree. </div><div><br></div><div>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.</div><span><font color="#888888"><div><br></div><div>Trent</div></font></span></div>
<br></div></div><span class="">_______________________________________________<br>
Python mailing list<br>
<a href="mailto:Python@lists.noisebridge.net" target="_blank">Python@lists.noisebridge.net</a><br>
<a href="http://www.noisebridge.net/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.noisebridge.net/mailman/listinfo/python</a><br>
<br></span></blockquote></div><br></div></div>
<br>_______________________________________________<br>
Python mailing list<br>
<a href="mailto:Python@lists.noisebridge.net">Python@lists.noisebridge.net</a><br>
<a href="http://www.noisebridge.net/mailman/listinfo/python" rel="noreferrer" target="_blank">http://www.noisebridge.net/mailman/listinfo/python</a><br>
<br></blockquote></div><br></div>