In this question, we consider the problem of finding an integer x in a given sor

Question

In this question, we consider the problem of finding an integer x in a given sorted array A[1 to n]. The array is sorted, so This is called binary search on a sorted array. Below we construct a function BinarySearch(A[1 to n], x) that returns True if x E A, and False otherwise. As the first try, compare x with A[1], A[2], ., A[n] in that order until x is found. This clearly takes time in the worst case, where T(n) denotes the running time of BinarySearch(A[1 to n], x) Now let us improve T(n) using divide and conquer. Instead of comparing x with A[1], A[2], ...., compare x with A[h] first where h: (b) Here is a function of n returning a definite value for every n. This divide and conquer should partition the given array into halves. Now our pseudo code is written as BinarySearch(A[1 to n], x) if n-1 and A1]-x return True else if n-1 and A[1] return False else if ? A [h] return else eturn

Explanation / Answer

a) O(n) .... As it will search maimum n times like linear search

b) h = (n+1-1)/2 .............. mid = (high -low+1)/2 for bnary search we compare with middle element

c) return BinarySearch(A[1.....h-1], x) as x < mid it will lie on left of mid of sorted array

d) return BinarySearch(A[h+1.....n], x) as x > mid it will lie on right of mid of sorted array

e) T(n) = T(n/2) + 1

f) O(log n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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