# Algorithm help

**URL:** <https://rubytalk.org/t/algorithm-help/19967>\
**Category:** ruby-talk\
**Created:** [5 August 2005 14:34 UTC](https://rubytalk.org/t/algorithm-help/19967 "2005-08-05T14:34:51Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Kroeger\_Simon\_ext](https://avatars.discourse-cdn.com/v4/letter/k/5daacb/32.png) [@Kroeger\_Simon\_ext](https://rubytalk.org/u/Kroeger_Simon_ext)\
**Post date:** [5 August 2005 14:34 UTC](https://rubytalk.org/t/algorithm-help/19967/1 "2005-08-05T14:34:51Z")

</div>

> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[5, 3, 0]

ok, this is sorted, but I thought it is sortet  
from smallest to largest. Reversing the array alone  
has O(n) complexity.

> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;harp:~ \> cat a.rb  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tests = [  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[0],  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[0,1],
> 
> [..snip..]
> 
> it is short though 😉

...but not made for reversed arrays. Here is a version  
that has O(log n) complexity for all cases (even large  
number of ranges) but is also made for sorted arrays  
(lowest to highest)

> **···**
>
> ------------------------------------------------------  
> def toRanges d  
> &nbsp;&nbsp;&nbsp;&nbsp;return d.size\>0 ? [d.first..d.last]: if  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(d.last - d.first)==d.size-1 || d.size==0  
> &nbsp;&nbsp;&nbsp;&nbsp;r1, r2 = toRanges(d[0...(d.size/2)]),  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;toRanges(d[(d.size/2)..-1])  
> &nbsp;&nbsp;&nbsp;&nbsp;r1.last.last+1\>=r2.first.first ? r1[0..-2]+  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[r1.last.first..r2.first.last]+r2[1..-1]:r1+r2  
> end
> 
> puts toRanges((1..40).to\_a + (123..789).to\_a +  
> &nbsp;&nbsp;&nbsp;&nbsp;[6789, 6790, 9998, 9999] )
> 
> ------------------------------------------------------
> 
> if you have to process reversed arrays the fastest way  
> would be to write another method for that case and call  
> only the right one based on (data.first \> data.last).
> 
> greets
> 
> Simon