A) Using the Binary Search algorithm. Write the algorithm in pseudocode. Analyze
ID: 3747017 • Letter: A
Question
A) Using the Binary Search algorithm. Write the algorithm in pseudocode. Analyze
the algorithm for time needed as the size n of the problem changes.
B) Suppose we write an algorithm called Ternary Search where instead of dividing the sorted
array into two parts, we search by dividing the relevant part of the array into three parts,
determine which part the item we are looking for appears, and recursively search for the item
in this part. Write this algorithm in pseudocode. Analyze the algorithm for time needed as
a function of the size n of the problem.
Explanation / Answer
Solution A : Binary Search : The only condition for using binary search is that the array should be in sorted order. Then only we could apply binary search on that. Now ,
Binary Search PseudoCode :
int binarysearch(int a[],int low,int high,int x) // array a should be in sorted order ,low=first index , high=last index , x is the element to be searched , function would return index of searched element if x found , otherwise return -1
{
while(low<=high)
{
mid=(low+high)/2
if(a[mid]>x)
return binarysearch(a,mid+1,n-1,x) // let n-1 is the last index of array a
else if(a[mid]<x])
return binarysearch(a,0,mid-1,x) // let 0 is the first index of array a
else if(a[mid]==x)
return mid // if element found , return index
}
return -1 // if element not found , return -1
}
Time Complexity : O(log n) in worst case
Now , if n=10 , time required would be O(log10)
if n=100 , time required would be O(log100)
if n=1000 , time required would be O(log1000)
if n=10000 , time required would be O(log10000)
if n=100000 , time required would be O(log100000)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.