How to find the smallest difference between two numbers in a sorted list using divide-and-conquer approach? For example,
(smallest-dif '(5 500 510 670 750 10000)) => 10
$\begingroup$
$\endgroup$
-
1$\begingroup$ Can you tell us what you have tried so far, and where you got stuck? Have you studied other classic divide-and-conquer algorithms (e.g., from an algorithms textbook), and did you understand how they work? Also, why is it necessary to use divide-and-conquer as opposed to some other method to solve this problem? $\endgroup$ – D.W.♦ Jul 3 '13 at 7:13
-
$\begingroup$ @D.W. This is because I'm learning divide-and-conquer now and I want to practice. However, I don't even have any idea how to start this problem using divide-and-conquer. I need some hints please. $\endgroup$ – user2185071 Jul 3 '13 at 15:17
-
$\begingroup$ Ahh, if you're trying to learn about divide-and-conquer, I suggest going about it a different way. Start by studying it in a textbook. Then do some practice problems from a textbook. If you get stuck, you can show what you've tried so far, what hasn't worked, and ask for a hint. $\endgroup$ – D.W.♦ Jul 3 '13 at 16:59
$\begingroup$
$\endgroup$
The smallest difference between two numbers in a sorted list is given by the difference between some consecutive numbers in the list. This can be found out in linear time without using a divide and conquer approach. Since you have a O(n) algorithm which is the least possible time required to solve this problem it is not advisable to use a divide and conquer approach.
$\begingroup$
$\endgroup$
Let's take your example. I'll show how to find the minimal difference, and hopefully you'll be able to generalize (though there's no divide and conquer involved). The minimal difference is always obtained at some consecutive elements. We compute all the relevant differences $500-5 = 495$, $510-500 = 10$, $670-510=160$, $750-670=80$, $10000-750=9250$, and take the minimum $10$.
answered Jul 3 '13 at 5:58
-
$\begingroup$ How do you find it in "divide and conquer" way? Do you have any hints? $\endgroup$ – user2185071 Jul 3 '13 at 6:01
-
$\begingroup$ Why do you need to use divide and conquer? I have given you a simple algorithm. Perhaps there is a mistake in the question. You should realize that in the end, you come up with these algorithms since you want to solve some problems, and in real life you never have to follow one or the other methodology. $\endgroup$ – Yuval Filmus Jul 3 '13 at 10:27
-
$\begingroup$ @YuvaiFilmus This is because I'm learning divide-and-conquer now and I want to practice. However, I don't even have any idea how to start this problem using divide-and-conquer. I need some hints please. $\endgroup$ – user2185071 Jul 3 '13 at 15:46
-
$\begingroup$ The divide and conquer approach here would be to divide the list into two halves, calculate the minimal distance in each, and compare the two distances to the distance between the elements at the border between the two halves. But that's a bit silly. $\endgroup$ – Yuval Filmus Jul 3 '13 at 17:10
