Question:
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'