Discrepancy in Week-5 Question 4

[2K22/A13/54 ARYAN GARG]

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.

Lets 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 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.

[NOC243 CS113]

Hi,

Let there be 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 left/first list or as first element in right/second list.
Let us take mid as 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 beings 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.

Thanks,
TA (The Joy of Computing using Python)

[PRATEEK]

Yes, the answer to Q.4  of  Week 5: Assignment 5 should have been   Binary: 11, Linear: 1024   .

The reply from the TA is not acceptable, they should have stated it clearly if there was something which needs to assumed before solving the question.

Also, it is not written there in the question that the target element exists in the list. Course TAs just assume anything in their head, but don't mention it in the question. Also, it is not necessary for the algorithm to end up in an error or exception, there are graceful ways for the algorithm to end its run.

As far as correctness of the answer is concerned with respect to computer science principles, it should be Binary : 11.

I don't understand why the course TAs are having a difficult time to understand this, why can't they just admit their mistake in evaluation of this question and re-evaluate the question. Don't they understand that these assignment scores affect our overall score.

I think that Course TAs are not from Computer Science background, and hence I request that this issue should be elevated to Prof. Sudarshan Iyengar.
I answered the question accurately by taking reference from trusted sources, still my marks got deducted. This is not fair.
Even after answering a question correctly, I'm not able to get the marks for it.

I am attaching the links of some authentic sources from where the course TA can check their facts.
https://stackoverflow.com/questions/61570880/how-is-maximum-key-compare-in-binary-search-1logn-not-logn

http://watson.latech.edu/book/algorithms/algorithmsSearching2.html#:~:text=The%20maximum%20number,N%2B1)%E2%8C%89

I executed this below mentioned code [ which is taken directly from the lectures of this course ] after adding a counter variable.

#q4
def binary_search(a,x):
    first_pos = 0
    last_pos = len(a)-1
    flag=0
    #Flag=0 means that the element has not been found yet
   
    count = 0
   
    while(first_pos<=last_pos and flag==0):
        count+=1
        mid = (first_pos+last_pos)//2
        if (x==a[mid]):
            flag = 1
            print("The element is present at pos: "+str(mid))
            print("The numeber of iterations are: "+str(count))
            return
        else:
            if (x<a[mid]):
                last_pos = mid-1
            else:
                first_pos = mid+1
   
    print("The number is not present")
   
a = []
for i in range(1,1025):
    a.append(i)

binary_search(a, 1024)

The output was :

The element is present at pos: 1023 The numeber of iterations are: 11
Please re-evaluate the question as soon as possible.
Thank you.

[Kamala Malar]

I agree with Prateek.

TA explanation was wrong , each iteration we used to find the mid element of the sub array. So if the item is found @ index 2. 

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

Again, a comparison here with mid, Comparisons = 10

R=[2], Mid=0

Final comparison here with mid, Comparisons = 11. This step is missing . 

@ Prof. Sudarshan Iyengar Sir Waiting for your clarification Sir/