# improve the running time

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

• 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$. – Danny Mar 28 '17 at 13:16
• 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. – njzk2 Mar 28 '17 at 18:59
• @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. – Danny Mar 29 '17 at 10:22
• There is no algorithm here. – Raphael Apr 4 '17 at 19:02
• 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. – Raphael Apr 4 '17 at 19:02