Sorting and searching are among some of the most frequent operations used in computing. Consider the following algorithm for bubble sort.

binarySearch(arr, size)

loop until beg is not equal to end

midIndex = (beg + end)/2

if (item == arr[midIndex] )

return midIndex

else if (item > arr[midIndex] )

beg = midIndex + 1

else

end = midIndex - 1

Source: https://www.mygreatlearning.com/blog/binary-search-algorithm/

Now think about the following questions. Use at least 2-3 complete sentences to answer each of the following questions.

Q1 - Why does binary search require an array (arr) to be sorted before the algorithm is applied?

Q2 - Explain the if / else if/ else control flow in language that even a young child could understand. A good example might be to reference a phonebook (i.e. the yellowpages).

Q3 - What happens if the middle number is not the one were searching for? How does the concept of a loop play a role in binary search?

Q4 - Consider the following array of numbers: [5, 3, 11, 9, 6, 8, 3, 10, 21, 15]

Lets say youre searching to see if 11 is in the list (I know, its obvious it is!). Show how a computer would implement binary search to find this value. List each iteration (as many as needed).

Iteration 1:

Q5 - Now lets say youre trying to find 16 (a number not in the array). Show how a computer would determine that 16 is not in the list using binary search. List each iteration (as many as needed).

Iteration 1:

Q5 - now that youve understood each iteration of the code, explain in plain language what this algorithm does. Imagine that you need to search a really long array of numbers (say, a million). This would be a tortuous task for a human. Explain how binary search makes this a trivial operation for a computer, which is great at doing redundant things!