Question 4: (a) How many items wl Binary Search examine at most when searching a

Question

Question 4: (a) How many items wl Binary Search examine at most when searching a sorted array of 453 elements? Show the array size at each step. (I mark) (b) How many items should the array have at least /at most for Binary Search to require one more iteration (i.e., to examine one more item)? (2 marks) (c) Apply Binary Search to the Sorted List below (an array of 16 elements) to try and find an item of key 'K'. Give the index values of the first, last, and midpoint elements of the sub-array that is searched at each step. (1 mark) y 0 1 2 3 4 5 6 7 8910 11 12 13 14 15 midpoint steplas #1 #2 15

Explanation / Answer

a)Binary Search deals with splitting an array in two each cycle and throwing half of this array away. So in the worst case scenario (the maximum number of comparisons) this array will be reduced down to only one element.
Therefore worst case, 9 comparisons are needed in 453 elements.
b)for 1 more execution i.e.10 we need atmost (2,pow 10) ie 1024 elements and atleast 455 elements.
c) step=1 , first =0, last=15 ,midpoint = 7(L)
  step=2 , first =0, last=6 ,midpoint = 3(E)
  step=3 , first =4, last=6 ,midpoint = 5(H)
  step=4 , first =6, last=6 ,midpoint = 6(J) Not found

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.