Search JAVA

Consider an approach to searching for a key in a sorted array in which we randomly choose an index between the two ends of the array, compare the item at that index with the search key and then either • If the item there equals the key, return the index • If the item there is larger than the key, recursively search to the left of index using the same strategy • If the item there is smaller than the key, recursively search to the right of the index using the same strategy
Write a function search(intO a, int key) to implement this searching algorithm.
Write recurrences that describe the average and worst case behaviors of this algorithm and, without formally solving them, explain what you think the answers will be and why.

×
New Download