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
$\begingroup$
$\endgroup$
7
-
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$– DannyMar 28, 2017 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$– njzk2Mar 28, 2017 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$– DannyMar 29, 2017 at 10:22
-
1$\begingroup$ There is no algorithm here. $\endgroup$– RaphaelApr 4, 2017 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$– RaphaelApr 4, 2017 at 19:02
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$– RaphaelApr 4, 2017 at 19:02