How can I use divide and conquer to improve the running time of this algorithm?
input: A sorted array of length n
output: the # of elements such that abs(A[i]) <= k
How can I use divide and conquer to improve the running time of this algorithm?
input: A sorted array of length n
output: the # of elements such that abs(A[i]) <= k
You have a sorted array of n elements.
If the first element is > k then no elements have absolute value ≤ k. (Why ?)
If the last element is < -k then no elements have absolute value ≤ k. (Why ?)
If the first element is ≥ -k and the last element is ≤ k then all n elements have absolute value ≤ k. (Why ?)
If neither of these criteria was fulfilled then we must have n ≥ 2 (why ?). Take a subarray containing the first n/2 elements, and a subarray containing the remaining n - n/2 elements, then count the elements with absolute value ≤ k in each subarray, and add the results.