Learning from Grokking Algorithms

[Zepher]

Hello all

I'm trying to learn algorithms from Grokking Algorithms by Aditya Y. Bhargava, but when I write the code, it doesn't show the same result like the writer. Can someone pointing out what's actually the problem?

def binary_search(list, item):
	low = 0
	high = len(list)-1
	while low <= high:
		mid = int((low + high)/2)
		guess = list[mid]
		if guess == item:
			return mid
		if guess > item:
			high = mid - 1
		else:
			low = mid + 1
		return None

my_list = [1, 3, 5, 7, 9]
print (binary_search(my_list, 3)) # => 1

The result supposed to be 1, but I got "None" result

None
[Finished in 169ms]

---

def findSmallest(arr):
	smallest = arr[0]
	smallest_index = 0
	for i in range(1, len(arr)):
		if arr[i] < smallest:
			smallest = arr[i]
			smallest_index = i
		return smallest_index
def selectionSort(arr):
	newArr = []
	for i in range(len(arr)):
		smallest = findSmallest(arr)
		newArr.append(arr.pop(smallest))
	return newArr

print(selectionSort([5,3,6,2,10]))

This one I got an error in code "newArr.append(arr.pop(smallest))" and "print(selectionSort([5,3,6,2,10]))"

Traceback (most recent call last):
  File "C:\Users\User\AppData\Local\Programs\Python\Python312\Hellow.py", line 16, in <module>
    print(selectionSort([5,3,6,2,10]))
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\User\AppData\Local\Programs\Python\Python312\Hellow.py", line 13, in selectionSort
    newArr.append(arr.pop(smallest))
                  ^^^^^^^^^^^^^^^^^
TypeError: 'NoneType' object cannot be interpreted as an integer
[Finished in 173ms]

Gribouillis write Jul-23-2024, 07:44 AM:
Please post all code, output and errors (it it's entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.

[deanhystad]

Indenting for return None is wrong in binary search. You do the same thing in findSmallest.

[Zepher]

Indenting for return None is wrong in binary search. You do the same thing in findSmallest.

What should I do? I'm completely newbie in this case, I don't even have any idea with the above codes because I'm just copy pasting from the book.

It's really surprising that they can release a book when the codes aren't working properly.

[deanhystad]

You made an error copying the code from the book. The code from the book is like this:

def binary_search(list, item):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = int((low + high)/2)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None   # <--- Notice change in indent.

Indenting in Python is syntax, not just a way to make the code look pretty. Indenting defines code blocks. In your version of binary_search the function returns None if the first guess is incorrect. This happens because the indenting for "return None" places it inside the block of code executing in the while loop. In the version posted above indenting places "return None" outside the while loop. "return None" does not execute until the "while low <= high:" loop has completed. Four spaces making all the difference here.

You make the same error in find_smallest(). Because of the indent error you return the first element instead of the smallest element. When you've removed all but the last element the for loop doesn't execute and the function returns None (default value for functions that don't execute a "return" statement). You get the error message when this happens.

[Zepher]

Indenting in Python is syntax, not just a way to make the code look pretty. Indenting defines code blocks. In your version of binary_search the function returns None if the first guess is incorrect. This happens because the indenting for "return None" places it inside the block of code executing in the while loop. In the version posted above indenting places "return None" outside the while loop. "return None" does not execute until the "while low <= high:" loop has completed. Four spaces making all the difference here.

You make the same error in find_smallest(). Because of the indent error you return the first element instead of the smallest element. When you've removed all but the last element the for loop doesn't execute and the function returns None (default value for functions that don't execute a "return" statement). You get the error message when this happens.

Oh man... I feel like it's really a stupid mistake.

Now the codes is working fine.

1
[Finished in 64ms]

[3]
[Finished in 63ms]

Thank you very much man, now I've learn what indent is.