PWC 263, Task 1 Target Index

Here's a little blog I wrote. You might want to read it note for note.

You are given an array of integers, @ints, 
and a target element $k.

Write a script to return the list of indices
in the sorted array where the element is the
same as the given target element.

Example 1

• Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2
• Output: (1, 2)
  • Sorted array: (1, 2, 2, 3, 4, 5)
  • Target indices: (1, 2) as $ints[1] = 2 and $ints[2] = 2

Dive right in

Well, the example gives it away, doesn't it? Sort the array and waddle up the list to the first index where $k exists. Then, because the array is sorted, all the other places where $k exists must be adjacent.

Or not

But hold on. In every algorithm we have some trouble, but when you sort you make it double.

All the $k together means we've effectively partitioned the array into three sets: elements that are less than $k, elements equal to $k, and the rest.

We don't have to sort the array at all. We just have to traverse the array and count the elements in the first two partitions.

sub targetIndex($k, @ints)
{
    my ($below, $same) = (0, 0);
    foreach ( @ints )
    {
        if    ( $_ < $k )  { $below++ }
        elsif ( $_ == $k ) { $same++ }
    }
    return [] if $same == 0;
    return [ $below .. ($same + $below - 1) ];
}

If $k doesn't appear at all, we can bail out by returning an empty list. $below and $same tell us the range of numbers we need in the answer.

$below = 1 # 1 element less than $k
$same  = 2 # 2 elements equal to $k
      {         } 
   1  {  2   2  }   3   4   5
  [0] { [1] [2] }  [3] [4] [5]
         ^   ^
         |   +---- $below + $same -1 = 1+2-1 = 2
  $below-+

The .. range operator makes short work of creating the sequence of numbers we want.

Put that range of numbers into an array, and we have our answer. This function is returning array references, not arrays, so the calling function will have to de-reference. In context, it might look like

say "(", join(",", targetIndex($Target, @ARGV)->@*), ")";

Now there is the blog I wrote. I hope you liked the way I code. Don't worry, be hacker.