There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
Agree with a comment or answer? Like () to up-vote the contribution!
does it matter what order the if statements go after we define the mid index & value? The check for mid value == target going first confuses me in the first test case. In the first test case the target is 9. At the end of the 2nd iteration of the while loop, the left pointer becomes 4 AFTER the mid value == target check. Why did it not go back to the top of the while loop to check for while 4 < 4
I got a bit confused with the values of right and left at first because I had another approach in mind going into the assignment. I was thinking the right and left indices would both be inclusive, meaning we would reach our final stop when left == right.
But the assignment prefers having an exclusive right index, meaning it’s 1 step outside of our search range (the way the range and slice functions work). So in this case when we’re looking for 9, the middle index in the first iteration becomes (0+5) // 2 = 2, we see that our target is larger than the middle value so we set left to 2+1=3. The middle index in the second iteration becomes (3+5)//2 = 4, the index of the 9 we’re searching for. Meaning we return before we reach the condition that terminates the while loop.
As for the order of the if-statements, they don’t really matter in this case since the variables used in the conditions aren’t altered until the next iteration, meaning all conditions are mutually exclusive. However since they’re mutually exclusive it makes sense to look for our base case before doing any more work.
In the iterative version of binary_search, why do we update left_idx = mid_idx +1 instead of left_idx = mid_idx?
def binary_search(sorted_list, target):
left_pointer = 0
right_pointer = len(sorted_list)
# fill in the condition for the while loop
while left_pointer < right_pointer:
# calculate the middle index using the two pointers
mid_idx = (left_pointer+right_pointer)//2
mid_val = sorted_list[mid_idx]
if mid_val == target:
return mid_idx
if target < mid_val:
# set the right_pointer to the appropriate value
right_pointer = mid_idx
if target > mid_val:
# set the left_pointer to the appropriate value
**left_pointer = mid_idx +1**
return "Value not in list"
This has to do with the rounding behavior of integer division. Take
left_pointer, right_pointer = 0, 9
A = left_pointer+right_pointer
mid_idx = A // 2
print(mid_idx)
Including mid_idx (here 4) results in searching the left half of the list twice. Notice how by contrast, the right_pointer gets set to mid_idx. Our goal is to deterministically make a disjoint split of the list for binary search.
) below.
) to up-vote the contribution!