FAQ: Survey of Computer Science - The Tale of Kenny - Optimization

This community-built FAQ covers the “Optimization” exercise from the lesson “Survey of Computer Science - The Tale of Kenny”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Code Foundations

FAQs on the exercise Optimization

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Why is it that when i use the binary search that it returns the same entry multiple times before moving forward?

Here you can find a screenshot of it. Image

4 Likes

It’s to do with the recursion as the list gets shortened.

If the middle value comes after the search term, the function recurses over the left half, else the right. Check again for relativity, recurse half again, and so on. We can see it only takes about half a dozen recursions.

Feed in a range of numbers to see a clearer picture…

binary_search(range(1000),679)
Checking the bookshelf and finding: 0
Checking the bookshelf and finding: 501
Checking the bookshelf and finding: 501
Checking the bookshelf and finding: 626
Checking the bookshelf and finding: 626
Checking the bookshelf and finding: 658
Checking the bookshelf and finding: 674
Checking the bookshelf and finding: 674
Checking the bookshelf and finding: 678

Found the book: 679
1 Like

May I suggest replacing the line
print("Checking the bookshelf and finding: {0}".format(lst[0]))
with
print("Checking the bookshelf and finding: {0}".format(lst[len(lst) // 2]))

That way the program displays the book in the middle of the selection, which seems more relevant to me than the book at the start of the selection.

1 Like

Could you please explain in a bit simpler language ?

2 Likes
def binary_search(lst, search_val):
  if len(lst) == 0:
    print("Book is not on the shelf!")
    return
  print("Checking the bookshelf and finding: {0}".format(lst[0]))
  mid = len(lst) // 2
  if lst[mid] == search_val:
    print("\nFound the book: {0}\n\n\n\n\n\n".format(search_val))
    return
  elif lst[mid] > search_val:
    binary_search(lst[:mid], search_val)
  else:
    binary_search(lst[(mid + 1):], search_val)

The simplest language is the code itself.

Why my binary seach does not work?

I wrote binary_search(bookshelf, "Do Androids Dream of Electric Sheep?") in my code as the exercise explains. Unfortunately, when I run the code I do not see the book found.

This is what is shown:

Checking the bookshelf and finding: 1st To Die
Checking the bookshelf and finding: 1st To Die
Checking the bookshelf and finding: 1st To Die
Checking the bookshelf and finding: Cat’s Cradle
Checking the bookshelf and finding: Cat’s Cradle
Checking the bookshelf and finding: Defending Jacob

Found the book: Do Androids Dream of Electric Sheep?

So, where is “Do Androids Dream of Electric Sheep?”

By the way, the linear search worked.

I don’t understand how inside the definition of a function the function is called within itself.

image

This will come up in the lessons, at some point, if it hasn’t already. It’s a concept known as recursion. Notice that the calls are inside a conditional, of which one is the base case (in this case, search_val is found) and the other two are recursive cases.

If you have the time to segue, look up the topic of recursion to gain a greater understanding. There are even a few examples here in the forums that you may glean something from.

1 Like

I also didn’t understood a single word about this… :exploding_head: