Refer to the sequence s1 = ‘C’, s2 = ‘G’, s3 = ‘J’, s4
= ‘M’, s5 = ‘X’
This algorithm looks for a value in a nondecreasing sequence and returns
the index of the value if it is found or 0 if it is not found.
1, sorted in nondecreasing order, a value key, i, and j
Output: The output is an index k for which sk = key, or if key is not in
the sequence, the output is the value 0.
binary_search(s, i, j, key){
if (i > j) // not found
return 0
k = (i + j)/2
if (key = = sk) // found
return k
if (key < sk) // search left half
j = k – 1
else // search right half
i = k + 1
return binary_search(s, i, j, key)
}
Show how the Algorithm above executes in case key = ‘C’
Mathematics Homework Solutions
#106875
Show, how the given binary search algorithm executes in case of given key value.
Given algorithm looks for a value in a nondecreasing sequence and returns the index of the value if it is found or 0 if it is not found.
Input: A sequence si, ...... ,sj (j >= i >= 1) sorted in nondecreasing order, a value key, i, and j
Output: The output is an index k for which sk = key, or if key is not in the sequence, the output is the value 0.
binary_search(s, i, j, key) {
if (i > j) // not found
return 0
k = (i + j)/2
if (key == sk) // found
return k
if (key < sk) // search left half
j = k - 1
else // search right half
i = k + 1
return binary_search(s, i, j, key)
}
Consider the sequence s1 = 'C', s2 = 'G', s3 = 'J', s4 = 'M', s5 = 'X'. Show how the algorithm executes in case key = 'C'.
Attached document gives statement by statement execution of each binary_search call, explaining the execution/non-execution of individual statements during the call. Additionally it counts the number of operations at algorithm level during each call, excluding the contribution from recursive call.
What is this?
By OTA - Overall OTA Rating
Sandeep Kumar, MTech - 4.9/5
Purchase Cost Now
$2.19 CAD (was ~$3.99)
Included in Download
- Plain text response
- Attached file(s):
- 106875_doc1.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case. - Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.
- Algorithm to convert to binary - The problem is from Numerical Methods. Please show each step of your solution and tell me the theorems, definitions, etc. if you use any. 3. The following algorithm... Please see attached.
- Trees and Graphs : Vertices, Nodes, Breadth-first Search Algorithm and Rooted Trees - 1. Use the breadth first search algorithm to find a spanning tree for the following connected graph. Start with A and use alphabetical order when there is a choice for a vertex. 2. For the follow ...
- Fractions in Binary - There are fractions in binary (floating points). Please convert 1.1 subscript 2 to decimal. Kindly show the steps. Thanks.
- Decimal to Binary Conversion of a Fraction - Please convert 1.32 subscript 10 to binary. Kindly show steps.
