Question

1. When keys are stored in an array in an ascending order, what will be the best running time to search a certain key from the array? Explain your answer.

Answer 1

When an array is sorted in ascending order, we can use binary search to search for a certain key in the array.
in binary search, we compare key with the middle element
and if key is greater than the middle element, then we search for key in right part of the array(because array is sorted in ascending order)
if key is lesser than the middle element, then we search for key in left part of the array
so, after each comparision we are essentially reducing the search space by half.
This algorithm takes O(log n) (logarithmic) time complexity.