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 Perl)
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: $pivot; 
	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);
	}
	
}