Question

Consider the following sorted int array:

1 3 4 5 7 9 10 12

If we search for the key value 10 in the array using the binary search algorithm, what is the sequence of indices that will be accessed in the array?

(Hint: For a sublist between index values low and high, the middle index is calculated using: (low + high) / 2. So you need to show the sequence of indices of the middle index in each pass.)

Question 40 options:

Answer 1

Searching for 10 in list [1, 3, 4, 5, 7, 9, 10, 12]
   low = 0, high = 7, mid = 3
   > Middle element in this list is 5
   > Compare Target (10) with middle element (5) of this list
   > Target value (10) is larger than this middle element 5
   > so, we have to search in right part of the list([7, 9, 10, 12])
Searching for 10 in list [7, 9, 10, 12]
   low = 4, high = 7, mid = 5
   > Middle element in this list is 9
   > Compare Target (10) with middle element (9) of this list
   > Target value (10) is larger than this middle element 9
   > so, we have to search in right part of the list([10, 12])
Searching for 10 in list [10, 12]
   low = 6, high = 7, mid = 6
   > Middle element in this list is 10
   > Compare Target (10) with middle element (10) of this list
   > They are the same. Target element (10) is found. so, binary search ends here.
It took a total of 3 comparisons using binary search