Explore BrainMass

Explore BrainMass

    Execution of Binary Search Algorithm

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 March 4, 2021, 7:32 pm 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.