Hi @kknechtel! Thank you for these resources. I especially liked your first link. The two main takeaways I got from reading that older but still instructive Wordpress article is to (1) ‘obtain a rubber ducky’ and (2) write technical specifications for each method (which I think are similar to docstrings) which includes stating preconditions and postconditions. I’ve attempted to do this below. But I still struggle. It is incomplete.
I begin with practicing Rubber Ducky Debugging as I analyze @barry-scott’s code first since it is ‘low hanging fruit’ and easier for me to understand and describe for starters. My self-narrative I have inserted in-line and then discuss what I learned and other considerations afterwards.
Here is Barry’s code with my annotations:
def binary_seek(ordered_list, value):
print('binary_seek(%r, %r)' % (ordered_list, value))
# Initialize center index:
center = len(ordered_list) // 2
# Declare recursive base case (correctly positioned):
if value == ordered_list[center]:
return f"Found at: {center}"
# In the case where the target value is less than the center value, proceed:
elif value < ordered_list[center]:
# Slice a new list based on the first half of the original list to process on the next recursive pass:
new_list = ordered_list[:center]
return binary_seek(new_list, value)
# In the case where the target value is to the right of the original center value, proceed:
else:
# Slice new list, but on the opposite side
new_list = ordered_list[center:]
# Seek value again this time in sliced list
return binary_seek(new_list, value)
data = [101, 444, 567, 812, 999, 1101, 1232, 1522, 1684, 222234]
value = 999
result = binary_seek(data, value)
print('Seeking %d: %r' % (value, result))
Which outputs this:
binary_seek([101, 444, 567, 812, 999, 1101, 1232, 1522, 1684, 222234], 999)
binary_seek([101, 444, 567, 812, 999], 999)
binary_seek([567, 812, 999], 999)
binary_seek([812, 999], 999)
Seeking 999: 'Found at: 1'
Barry’s testing methodology is very helpful because the problem is now clear: Every time the recursive function is called, the list being processed becomes smaller and smaller. Once the base case is hit, the index being “Found” is the index of the reduced list, not the original list. Before using Barry’s output technique with print statements, using my debugger I could see a similar pattern. I will try to combine rubber ducky annotations with my debugger in this way going forward.
In Barry’s script, there are no left/right mechanisms any more. I think Barry may have removed them just to make it easier to teach and highlight the error I was making. But I am pretty sure right / left are still required to achieve a working binary search algorithm.
The problem now is I can’t Rubber Ducky my way to a different solution yet.
What I can do is use Karl’s line of questioning as guidance and to persevere as far as I can.
Before I get started, I think it is safe to toss out the idea of recursively processing the slicing of smaller and smaller temporary lists. That’s gone.
Here goes my feeble attempt at answering Karl’s questions:
Based on these questions, if I were to rewrite my script from scratch, here is a docstring written in free-hand (which after writing it, seems to more so resemble pseudo code than a formal docstring).
When the function is called the first time, these variables need to be initialized:
- The
leftvariable start at0, - The
rightmust start at the total length of the list minus 1 (so:len(ordered_list)-1), - The
centervalue needs to be an integer value half way between the farthest left point and right point. This can be accomplished with floor division (in this way:(left+right)// 2or(len(ordered_list)-1)//2. - Shortly after initializing the above variables, the base case needs to be promptly established (this is always true for recursion in general where the base case appears at the top and subsequent conditions come later).
- If the base case is not triggered, the script should proceed to define the next condition which is to evaluate if the target
valueis smaller than the value at thecenterindex. If this condition tests true, then the function is called recursively to seek the targetvalueagain but this time thecenterindex becomes the newrightindex and the newcenteris re-calculated using a similar floor division operation. - In the only other possible case (
else:) in the event where the value is greater than the item at the originalcenter, proceed to call the function recursively until the base case is hit (in the opposite direction to the right instead of to the left).
I’ve scrapped the approach where I am slicing the ordered_list into new_lists at each recursive function call. That doesn’t work as expected as Barry helped explain and as I then demonstrated.
At each recursive call, what I need to do is slightly shift left and right pointers as well as the center index values rather than slicing the list. I get that much. While this seems to be the key crucial change I need to make now, I really don’t know how to model this variation in the next iteration of my script. I can’t make the leap from this English written quasi-pseudo code understanding to Python code. I am all frazzled.
At each recursive call the list and target value must always remain the same. Those are static variables. Previously my list was not static and that was the problem. The only variables which should vary at each recursive function call I would think are center, left, and right. But again, I don’t know how to model these variable re-assignments in Python within the two conditional case declarations.
That’s all I got. I only feel marginally closer to understanding a basic binary search algorithm compared to before.
Special thanks to @kknechtel and @barry-scott for their help and insight. Further tips and suggestions on how to improve my pseudo code welcome. I am open to new ideas on how to better approach the next iteration of my binary seek function in Python.
