Lets say I have an array with sorted sequences of numbers (Example: 1,2,5,6,7,14,15,16), how would you go about identifying the largest gap in the sequence? In my example the largest gap would be 7-14.
I feel like there should be an elegant way to do this, but my brain doesn’t work
you can’t get the result without traverse every elements
max_gap = 0
index = 0
for i=1 to arr.count - 1 where max_gap < (diff = arr[i+1] - arr[i]) do ( max_gap = diff; index = i )
[ max_gap, index, index + 1 ]if that’s what you looking for , you need have done by yourself
traverse every element not elegant a bit
Actually , there’s a way to get the result without traverse all , calls dichotomy , if your date is large and close to each , such as numerical score , or record of temperature change etc , use
dichotomy may ever faster than normal traverse
an example below
sel=for i = 1 to 100000 collect (random 0 100000)
sort sel
--Normal traverse
st = timestamp()
(
max_gap = 0
index = 0
for i=1 to sel.count - 1 where max_gap < (diff = sel[i+1] - sel[i]) do ( max_gap = diff; index = i )
print ([ max_gap, index, index + 1 ] as string)
)
format "Normal Search Time: %ms\n" (timestamp()-st)
--Dichotomy
st = timestamp()
(
num = (sel[sel.count]-sel[1])/(sel.count-1)
indexsel = #()
fn getmaxgap f c l =
(
if sel[l]-sel[f] >= num do
(
num = amax #((sel[l]-sel[f])/(l-f),num)
if c - f > 1 and sel[c]-sel[f] > num then
getmaxgap f ((c+f)/2) c
else
(
if sel[c] - sel[f] > num then
(
num = sel[c] - sel[f]
indexsel = #(#(f,c))
)
else if sel[c] - sel[f] == num do append indexsel #(f,c)
)
if l - c > 1 and sel[l]-sel[c] > num then
getmaxgap c ((l+c)/2) l
else
(
if sel[l] - sel[c] > num then
(
num = sel[l] - sel[c]
indexsel = #(#(c,l))
)
else if sel[l] - sel[c] == num do append indexsel #(c,l)
)
)
)
getmaxgap 1 (sel.count/2) sel.count
print num
print (indexsel as string)
)
format "Dichotomy Search Time: %ms\n" (timestamp()-st)
under no circumstances can a “dichotomy search” be faster than a one-way linear iteration.
so how you explain what I post
dichotomy use more steps to calculate , but it skips lot’s data