A binary search is to be performed on the list: 1 , 5 ,10 , 13 , 48 , 68 , 100 , 101 How many comparisons would it take to the find the numb

Question

A binary search is to be performed on the list: 1 , 5 ,10 , 13 , 48 , 68 , 100 , 101 How many comparisons would it take to the find the number 101?

in progress 0
Amity 5 months 2021-09-03T09:09:47+00:00 1 Answers 92 views 0

Answers ( )

  1. Sapo1
    0
    2021-09-03T09:10:52+00:00
    Reply

    Answer:

    3 comparisons

    Step-by-step explanation:

    Given:

    List: 1 , 5 ,10 , 13 , 48 , 68 , 100 , 101

    Required

    Determine the number of comparisons to get to 101

    The length of the list is 8. So, the first index is 0 and the last is 7.

    We have:

    List[0] = 1   List[1] = 5   List[2] = 10     List[3] = 13    

    List[4] = 48    List[5] = 68    List[6] = 100    List[7] = 101

    Initially:

    begin = 0 — first index

    end = 7 — last index

    Start by calculating the mid-item

    mid = \frac{1}{2}(begin + end)

    mid = \frac{1}{2}(0 + 7)

    mid = \frac{1}{2}(7)

    mid = 3.5

    mid = 4 — approximated.

    The mid-index is 4 and the item is:

    List[4] = 48

    101 is on the right of 48.

    So, we calculate the new begin index.

    begin = mid + 1

    begin= 4 +1

    begin = 5

    Calculate mid

    mid = \frac{1}{2}(begin + end)

    mid = \frac{1}{2}(5 + 7)

    mid = \frac{1}{2}(12)

    mid= 6

    The mid-index is 6 and the item is:

    List[6] = 100

    101 is on the right of 100.

    So, we calculate the new begin index.

    begin = mid + 1

    begin = 6 +1

    begin= 7

    Calculate mid

    mid = \frac{1}{2}(begin + end)

    mid = \frac{1}{2}(7+7)

    mid = \frac{1}{2}(14)

    mid = 7

    At this point, the mid-index is at 101

    i.e.

    List[7] = 101

    This implies that, we have located 101.

    So far, we made 3 comparisons

Leave an answer

Browse

Giải phương trình 1 ẩn: x + 2 - 2(x + 1) = -x . Hỏi x = ? ( )