Share
Explore BrainMass

Execution of Binary Search Algorithm

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'.

Attachments

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.

$2.19