1. Position > Pivot (midpoint in the array)
   • in target
   • not in target
2. Position < Pivot (midpoint in the array)
   • in target
   • not in target

use strict;
use Data::Dumper;

# target reion
my @a = ("100_200","210_310","400_450","475_600", "680_900");
my $query_snp = 615;

my $line = quicksort(\@a, \$query_snp);

print "$$line";

# loosely based on the quicksort algorithm (Mastering Alorithms with P
+erl)
sub quicksort
{
    my $array     = shift;
    my $snp       = shift;
    my $start_idx = 0;
    my $end_idx = scalar @$array - 1; 
    my $mid_point    = int( ( $end_idx - $start_idx)/2 );
    my $pivot = $start_idx + $mid_point;
    
    my ($current_start , $current_end) = split /\_/, $array->[$pivot];
    my $current_start_idx = $$snp < $current_start ? $start_idx: $pivo
+t; 
    my $current_end_idx   = $current_start_idx ==$start_idx ? $pivot: 
+$end_idx;
    
    my $new_array = [ @$array[$current_start_idx..$current_end_idx] ];
    my $out_line; 
    my ($new_array_ele1_start,$new_array_ele1_end) = split /\_/, $new_
+array->[1];
    
    if( $$snp >= $current_start && $$snp <= $current_end)
    {
        $out_line = "$$snp\t$current_start\t$current_end";
        return(\$out_line);
    }
    elsif( $$snp < $new_array_ele1_start)
    {
        $out_line = "$$snp\tNOT_IN_TARGET";
        return(\$out_line);
    }
    else
    {
        quicksort($new_array, $snp);
    }
    
}
[download]