I have made my own index finder before my teacher covered the topic. For some reason, mine is about 21.5%~ slower. Each command makes the same number of guesses, but the class version makes said guesses quicker for some reason. Can someone explain this to me?
Your version starts by using the CONTAINS block to check if the desired item is in the list. This means you’re effectively searching twice. What’s more, CONTAINS doesn’t assume the list is sorted, so it does O(n) comparisons instead of O(lg n).
But if your list is large, I think you should see less of a difference, because all of that is swamped by the call to SORTED, which takes O(n lg n) comparisons to sort the input list. You’d get more realistic timing comparisons if you sort the input before you call the two lookup procedures, and don’t include that in the timing.
By the way, you don’t need to use stop [this block V] after saying “item not in list” in your version, and you don’t need it after saying what the index is in the class version. stop [this block V] is only required if you want to stop the block prematurely, that is to say that there is still some program beneath the script that you don’t want to run:
if <some condition> {
say [I'm gonna stop]
stop [this block V]
}@>
say [I'm gonna continue]
do other stuff
The block will automatically end when it reaches the end of the script, so often times stop [this block V] is not needed.
Could you share the entire initial exercise with us? I find this interesting…
This is the binary search, right?
Yes, it is. I’m not entirely sure what you mean by initial exercise, but we started by making a number guessing game the day before (computer guessing player num). The next day we made the binary search. Here’s that project:
(“feedback for computer” is decided by button presses on the screen, can be played here.)
The “bones” of both are very similar, which is why we started with the game. A fun way to sneakily teach binary searches.
Teacher notes/exercise
The only real notes we got were to reference the guessing game… I apologize for not being able to give more… Besides that, we followed Unit 5 Lab 1: Algorithms, Page 2 of bjc?
Thk, that’s exactly what i want…
I removed that part of mine, and now both programs run at about the same speed, mine maybe like 1~5% faster (Seems to changes depending on shuffle?). My list (element size of 250) is shuffled then sorted in the block and gets through everything in 9.5 seconds on average. However, one element doesn’t seem to be getting added to the list? I checked if my for i loop to find ever element was accurate, and it was, but the table is still one item short? Here’s the edited code:
