Explore BrainMass

Execution of Binary Search Algorithm

See the attached file.
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'.

© BrainMass Inc. brainmass.com June 20, 2018, 9:37 am ad1c9bdddf


Solution Summary

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.