Binary search task for sms-online.com

Assert_binsearch.pl

#! /usr/bin/perl

use strict;
use warnings;
use ImyaFamiliyaLatinitseyFindIndex;

# Make sure that we have the say command availible
sub say { print @_, "\n" }

# Create a class instance
my $finder = new ImyaFamiliyaLatinitseyFindIndex();

# Assert that the finder is working correctly
sub assert {
    # Collect arguments
    my $arrayRef = shift;
    my $toFind   = shift;

    # Call the finder function
    my ($index, $steps) = $finder->find($arrayRef, $toFind);

    # Print our result
    say '-'x50;
    say 'From array of size ', scalar @$arrayRef, ':';
    say $toFind, ' was found at index [', $index, '] closest(', @$arrayRef[$index] ,')  taking ', $steps, ' steps!';
    say '-'x50;
};

# Generated integer data for basic assertion
my $intData = [0, 0, 1, 2, 2, 3, 3, 5, 6, 6, 7, 8, 8, 9, 11, 13, 13, 13, 13, 14, 15, 16, 16, 18, 19, 21, 21, 22, 22, 23, 25, 27, 29, 29, 31, 32, 32, 32, 33, 34, 36, 36, 37, 38, 40, 40, 41, 41, 42, 43, 43, 43, 45, 46, 46, 48, 48, 48, 49, 50, 50, 51, 53, 55, 56, 59, 59, 63, 63, 64, 64, 65, 65, 67, 67, 71, 73, 73, 74, 75, 76, 76, 77, 79, 81, 81, 81, 81, 82, 83, 85, 86, 88, 88, 88, 89, 92, 93, 93, 94, 95, 95, 96, 96, 98, 99, 99, 110, 121, 137, 176, 181, 182, 182, 186, 198, 200, 205, 207, 222, 231, 247, 257, 266, 275, 275, 291, 309, 311, 320, 328, 337, 346, 348, 359, 370, 374, 402, 434, 437, 451, 463, 472, 480, 482, 483, 487, 493, 498, 499, 525, 536, 572, 582, 582, 597, 601, 618, 620, 623, 624, 624, 628, 628, 628, 631, 642, 650, 653, 672, 674, 686, 695, 716, 722, 734, 736, 745, 765, 777, 778, 779, 785, 786, 812, 816, 849, 857, 884, 897, 897, 923, 926, 939, 948, 967, 972, 986, 993, 995];

# Make sure that everything is ok with integers
assert($intData, 7);
assert($intData, 303);

# Generated floating point data for floatation assertion
my $floatData = [0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14, 0.15, 0.16, 0.17, 0.18, 0.19, 0.2, 0.21, 0.22, 0.23, 0.24, 0.25, 0.26, 0.27, 0.28, 0.29, 0.3, 0.31, 0.32, 0.33, 0.34, 0.35, 0.36, 0.37, 0.38, 0.39, 0.4, 0.41, 0.42, 0.43, 0.44, 0.45, 0.46, 0.47, 0.48, 0.49, 0.5, 0.51, 0.52, 0.53, 0.54, 0.55, 0.56, 0.57, 0.58, 0.59, 0.6, 0.61, 0.62, 0.63, 0.64, 0.65, 0.66, 0.67, 0.68, 0.69, 0.7, 0.71, 0.72, 0.73, 0.74, 0.75, 0.76, 0.77, 0.78, 0.79, 0.8, 0.81, 0.82, 0.83, 0.84, 0.85, 0.86, 0.87, 0.88, 0.89, 0.9, 0.91, 0.92, 0.93, 0.94, 0.95, 0.96, 0.97, 0.98, 0.99];

# Make sure that everything is working with floating point data
assert($floatData, -0.1);
assert($floatData, 1.0);
assert($floatData, 0.785);
assert($floatData, 0.223);

ImyaFamiliyaLatinitseyFindIndex.pm

#! /usr/bin/perl

use strict;
use warnings;

=begin comment

You are given an array of a large number of elements sorted in ascending order.

@a = (1,2,3,4,5,6,7,8,9,10)

You need to write a function which will find the index of the array element value which is closest to the passed in function arguments.

Code must be execute in the form of a class (i.e., there must be a method that returns a new instance) with the name ImyaFamiliyaLatinitseyFindIndex.pm.

The class object must have the find method, which takes the input sought value and a reference to an array.

The method should return an array of two elements
    - The index of the item in the array
    - The number of steps (number of comparisons).

=cut

package ImyaFamiliyaLatinitseyFindIndex;

sub new
{
    # Nothing needs doing here, just create the class default
    my $class = shift;
    my $self = {};
    bless $self, $class;
    return $self;
}

sub find_recurse {
    my ($arrayRef, $toFind, $min, $max, $steps) = @_;

    # Setup the steps parameter
    $steps = $steps || 0;

    # Find the median index of the selected slice
    my $medIndex = int($min + ($max - $min) / 2.);

    # Find the median of the selected numbers
    my $med = @$arrayRef[$medIndex];

    # Have we come very close to finding the index?
    if ($max - $min < 2) {

        # Look at the values of the $min and $max in the array
        my $minVal = @$arrayRef[$min];
        my $maxVal = @$arrayRef[$max];

        # Is the upper closest to the search parameter?
        if ($toFind - $minVal > $maxVal - $toFind) {
            return ($max, $steps);
        }

        # Return the index of the current iteration
        return ($min, $steps);
    }

    # increment the number of searches performed
    $steps += 1;

    # Is the sought item in the upper half?
    if ($toFind > $med) {
        return find_recurse($arrayRef, $toFind, $medIndex, $max, $steps);
    }

    # Is the sought item in the lower half?
    elsif ($toFind < $med) {
        return find_recurse($arrayRef, $toFind, $min, $medIndex, $steps);
    }

    # We've found the value!
    else {
        return ($medIndex, $steps);
    }
}

sub find {
    # Collect arguments
    my ($self, $arrayRef, $toFind) = @_;

    # Make sure the number is within the range of the array
    if ($toFind >= @$arrayRef[scalar @$arrayRef - 1]) {
        return (scalar @$arrayRef - 1, 1);
    }

    # Make sure the number is not too small
    if ($toFind <= @$arrayRef[0]) {
        return (0, 1);
    }

    # Start a binary search tree and return the closest number found
    return find_recurse($arrayRef, $toFind, 0, scalar @$arrayRef - 1)
}

1;