cp-find-index.pl

#!/usr/bin/perl

use Modern::Perl;
use Carp qw/confess/;
use constant ARRAY_SIZE => 1_000_000;
use constant ITER_N     => 1_000;

# ------------------------------------------------------------------------------
# Поиск индекса ближайшего к заданному элемента отсортированного массива. 
# Возвращает индекс в массиве и количество шагов, которое понадобилось
# для поиска.
# ------------------------------------------------------------------------------
my @data;
push @data, int( rand(ARRAY_SIZE) ) for 0 .. ARRAY_SIZE;
@data = sort { $a <=> $b } @data;

for ( 0 .. ITER_N ) {
    my $n = int( rand(ARRAY_SIZE) );
    my ( $idx, $steps ) = find_nearest( $n, \@data );
    printf "N = %u, index: %u (%u), steps: %u\n", $n, $idx, $data[$idx], $steps;
}

# ------------------------------------------------------------------------------
sub find_nearest
{
    my ( $n, $array ) = @_;

    my ( $first, $last, $steps ) = ( 0, $#{$array}, 0 );

    while ( $first <= $last ) {
        ++$steps;
        confess 'Something wrong!' if $steps > $#{$array};

        # Не ($first + $last) / 2! Так можно влететь на результат < 0,
        # если длина массива > INT_MAX / 2 
        my $mid = $first + int( ( $last - $first ) / 2 );
        if ( $n < $array->[$mid] ) {
            $last = $mid - 1;
        }
        elsif ( $n > $array->[$mid] ) {
            $first = $mid + 1;
        }
        else {
            return ( $mid, $steps );
        }
    }
    return ( $array->[$first] - $n ) < ( $n - $array->[$last] )
        ? ( $first, $steps )
        : ( $last, $steps );
}

# ------------------------------------------------------------------------------
1;