# 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 March 4, 2021, 7:32 pm ad1c9bdddfhttps://brainmass.com/computer-science/sorting/execution-binary-search-algorithm-106875

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