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
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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$.