Question
Consider function search( elm , low , high , myArray ) that searches for the value elm in the array myArray between the indexes low
Consider function search(elm, low, high, myArray) that searches for the value elm in the array myArray between the indexes low and high and returns the index where elm is found in the array or returns -1 if not found.
For example, if myArray is [4, 7, 8, 9, 12, 56], then you have the following:
search(12, 0, 5, myArray) returns 4
search(10, 0, 5, myArray) returns -1
Now consider the linear and binary algorithms below for the function search:
Linear Search
Function search(elm,low,high, myArray)
index = low
While(index <= high)
If myArray[index] == elm then
Return index // found
Else index = index + 1
End While
Return -1 // not found
End Function
Binary Search
Function search(elm,low,high, myArray)
While(high >= low) then
mid = (low + high) / 2
If (myArray[mid] == elm
Return mid; // found
Else
If (myArray[mid] > elm) then // search in the left half
high = mid-1
Else // search in right half
Low = mid +1
End While
Return -1 // not found
End Function
Complete the following:
- How many iterations are performed in each algorithm for the function call search(12, 0, 6, myArray) if myArray = [2, 3, 6, 9, 12, 15, 19]?
- Which of these two algorithms runs faster?
- Why do you believe that one runs faster than the other?
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started