Above is a screenshot of a quiz question I got wrong and don’t understand the explanation for.
How are we reducing the input by half with each interation? If target does not exist, ie. mid_value is always > or < target, then with each iteration we are moving either the end or starting index over by 1, and then searching again.
In the worst case scenario, the start and end indices would both be moved to the middle, and we’ll have traversed the entire list once, no?
One possible explanation I can think of is that since we are calculating start_idx + end_idx // 2, then we’ll have produced a bunch of identical searches that aren’t required; but as far as the code is concerned, I think the while loop still performs the full loop on each redundant search?