week-5 Question-4 Discrepancy

Week-5 Question-4 Discrepancy

Student's Logic:

Hi,
I wanted to bring up an issue with the number of iterations needed in binary search. In the problem, it's mentioned that binary search takes 10 iterations for a list of size 1024, but it should actually be 11 iterations.

If we start with a list of size 1024, the binary search will first check the middle element, splitting the list in half repeatedly. The number of iterations in binary search for a list of size n is given by log2(n) + 1. So, for 1024 elements:

• log2(1024) = 10, which means there are 10 splits.
• However, we also need to account for the initial check before the first split, making the total number of iterations 11.

Let's take it for a smaller list of 2 elements, say {1, 2} and target=2, first s=0, e=1. This gives mid=0, this would be the first comparison since arr[mid] < target so s=mid+1, so s=1 and e=1. Again mid=1, now arr[mid]==2 and hence we exit the loop now. We cannot ignore the last iteration since the target element might be 3 and we do not know for sure that the last element is the target element or not. Here also we took log2(2)+1 iterations. Extending this logic 11 should be the correct answer.

Thanks for your attention to this detail. I hope this clarifies the discrepancy.

Tutor's Explanation:

Hi,

Let there be a sorted list of 1024 elements. Since 1024 is a power of 2, there does not exist a true mid, which separates the list into two equal lists.

Such as 3 in this list - [1,2,3,4,5], here 3 is mid and separates into two lists ([1,2],[4,5]) if the element needed to be found is not the mid.

While dividing the list into two lists, we can consider mid as the last element in the left/first list or as the first element in the right/second list. Let us take mid as the last element in the left/first list.

Also, the question assumes that the target element exists in the list. If it doesn't exist, it results in an error/exception case, where the algorithm fails to find an element.

Let us put the element we need to search at index 1, to get the maximum possible iterations. For simplicity, it is considered here that indexing begins from 1.

So, [1,2,3,4......1024] becomes

• L = [1...512], R = [513....1024], Mid = 512
• We do a comparison here with mid, Comparisons = 1
• L = [1...256], R = [257...512], Mid = 256
• Again, a comparison here with mid, Comparisons = 2
• L = [1...128], R = [129...256], Mid = 128
• Again, a comparison here with mid, Comparisons = 3
• L = [1...64], R = [65...128], Mid = 64
• Again, a comparison here with mid, Comparisons = 4
• L = [1...32], R = [33...64], Mid = 32
• Again, a comparison here with mid, Comparisons = 5
• L = [1...16], R = [17...32], Mid = 16
• Again, a comparison here with mid, Comparisons = 6
• L = [1...8], R = [9...16], Mid = 8
• Again, a comparison here with mid, Comparisons = 7
• L = [1...4], R = [5...8], Mid = 4
• Again, a comparison here with mid, Comparisons = 8
• L = [1...2], R = [3...4], Mid = 2
• Again, a comparison here with mid, Comparisons = 9
• L = [1], R = [2], Mid = 1
• Final comparison here with mid, Comparisons = 10

Element Found.

Even if the element to be found is at index 2, we would still require only 10 comparisons.

For reference visit here