5. Fast searching in sorted array. Given an array of integers A sorted in ascend

Question

5. Fast searching in sorted array. Given an array of integers A sorted in ascending order and an integer B, describe a fast algorithm that finds if B is in A, where n is the length of A. Hint: check B against the middle element of A, A[n/2]; if B is less than A[n/2], continue your search in the left half of A, else continue your search in the right half of A.
a. Give a high-level step-by-step description of algorithm.
b. Give a pseudocode description of the algorithm.
c. Trace the algorithm for A = {1, 3, 4, 6, 7, 7, 9, 12, 19, 22, 30, 100}, B = 1, then for B = 100, then for B = 9.
d. Explain why the running time is log2n. Hint: how many times can a number be divided by 2 before you get 1? If log2n = a, then n = 2a.


If you have any idea with any a , b c, d please help me. Thank you.

Explanation / Answer

This is known as binary search Herer is a recursive algoritm function binarySearch(a, value, left, right) if right

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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