-2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Hint: You are looking for the number of elements in an array $A$ which are $\le k$. The array is sorted, so you only need to find the index $j$ of the array such that $A[j-1]\le k$ and $A[j]>k$. $\endgroup$ – Danny Mar 28 '17 at 13:16
  • $\begingroup$ Hint: what you are looking for is the same as, say, finding the number of pages before the page that has the word "elephant" in a dictionary. With the obvious twist that your dictionary has negative letters, and that a negative elephant may be a thing, and that the pages you want also are after the negative elephant. Weird dictionary. $\endgroup$ – njzk2 Mar 28 '17 at 18:59
  • 2
    $\begingroup$ @Yuval Filmus I thought that the question is not appropriate to directly present the solution, because the style of the question indicates that the questioner has not done a lot of effort to make progress. $\endgroup$ – Danny Mar 29 '17 at 10:22
  • 1
    $\begingroup$ There is no algorithm here. $\endgroup$ – Raphael Apr 4 '17 at 19:02
  • 2
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Apr 4 '17 at 19:02
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.