ALGORITHM3 The Binary Search Algorithm. an: increasing integers) procedure binar

Question

ALGORITHM3 The Binary Search Algorithm. an: increasing integers) procedure binary search (x: integer, a1,a2, i:= 1 {i is left endpoint of search interval } = n {j is right endpoint of search interval} while ij i#x > am then i := m + 1 else j := m if x = ai then location := i else location := 0 return location location is the subscript i of the term a equal to x, or 0ifx is not found) 26. Change Algorithm 3 so that the binary search procedure compares x toam at each stage of the algorithm, with the algorithm terminating if x = am, what advantage does this version of the algorithm have? 2. (20 points) Exercise 26, p. 203. Provide pseudocode and complexity for this algorithm. Change Algorithm 3, p. 195, so that the binary search procedure comparesr to am at each stage of the algorithm, with the algorithm terminating if am (a) Write what an advantage has this version of the algorithm. (b) Write a formula for a function which expresses the number of comparisons for the elements of a sorted sequence a,... , an against the target z in the worst and the best cases. (c) Classify the algorithm in the worst case using the big-O asymptotic notation.

Explanation / Answer

26.. Changes in the current algorithm are as follows :

binarySearch(x : iteger, a1,a2,......an : increasing integers )

i :=1; (left end point )

j:=n (right endpoint)

while i < = j. // first change, we will have go till the end in case element to be searched is in the last

m : = [ ( i + j )/2)]

if x = am then i = m , break (exit while) // Second change, we need to search for the equality if the middle element is the element to be searhed if this is the case then we can simply exit the loop.

if x > am then i = m+1;

else j = m-1;

if x = ai then location = i

else location = 0;

return location;

a) Advantage of this versio of algorithmm

One major advantage of this verion of algorithm is that if the element to be searched is the middle element then it can be found in the first iteration itself and gives the time complexity of O(1). If the searched element is less than the middle element then we need to search only the left side of middle and right side if it is greater than than the middle. and by doing so the list is divided into half in each iteration and even in the worst case it gives the time complexity as O(log n). which is much less than if we search in linear fashion.

b) Formula for the worst case for the above algorithm

T(n) = T(n/2) + 1; // here n/2 is the number of comparison made by lthe alogorithm and 1 denottes that 1 comparison which will always take place. even if there is only one element Worst case will occur if the elemet to be searched is either in the starting or the end of the list.

Formula for the best case for the above algorithm

T(1) = 1 // Best case will occur when the element is found ecactly in the middle leaving to only one comparison to be made.

c) Classifcation of algorithm i the worst case

In the worst case the algorithm wth the list of n numbers in n/2 times. with comparison occur in each division.. That gives the worst case time complexity of O(log n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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