Skip to content

Instantly share code, notes, and snippets.

@western

western/AndrewPFindIndex.pm

Last active February 27, 2017 15:50
Show Gist options
  • Save western/e52acd80af18355a5be676de51a5e1be to your computer and use it in GitHub Desktop.
Save western/e52acd80af18355a5be676de51a5e1be to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. western revised this gist Feb 27, 2017. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions AndrewPFindIndex.pm
    View file
    Original file line number Diff line number Diff line change
    @@ -5,7 +5,7 @@ use strict;
    use warnings;
    use Data::Dumper;

    use List::MoreUtils;


    # sorted array
    my $arr = [1,2,3,5,95,97,100];
    @@ -24,8 +24,7 @@ sub new{

    sub find{
    my $o = shift;
    my ($el) = @_;


    my ($word) = @_;
    my $low = 0;
    my $high = @$arr - 1;
  2. western created this gist Feb 27, 2017.
    49 changes: 49 additions & 0 deletions AndrewPFindIndex.pm
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@

    package AndrewPFindIndex;

    use strict;
    use warnings;
    use Data::Dumper;

    use List::MoreUtils;

    # sorted array
    my $arr = [1,2,3,5,95,97,100];

    sub new{
    my $c = shift;
    my $class = ref $c || $c;
    my %arg = @_;

    my $o = {};
    bless $o, $class;

    return $o;
    }


    sub find{
    my $o = shift;
    my ($el) = @_;

    my ($word) = @_;
    my $low = 0;
    my $high = @$arr - 1;
    my $step = 0;

    while ( $low <= $high ){
    my $try = int( ($low+$high) / 2 );
    $step ++;

    $low = $try+1, next if $arr->[$try] < $word;
    $high = $try-1, next if $arr->[$try] > $word;

    return [$try, $step];
    }

    [undef, $step];
    }


    1;