PWC 263.1 Don't Sort It, Be Happy

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.

Comments

[Barbe Vivien]

Hi Bob, thanks for your inspiring article. An interesting approach. However, there's a sentence that keeps playing in my mind when analyzing your text: don't make me think (the motto I learned from my students). IMHO, sorting the array and checking if $k has a match, providing the requested indices, is more straightforward than your approach, at least for me. Gives your solution better a performance? Are there other advantages? Anyway, thanks again! Best regards, Reinier

[Bob Lied]

Sorting is probably O(n log n), compared to one pass over the array O(n), so it will give better performance, if the arrays were bigger or the function was called enough times. Also, sorting the array will make a copy of the array, so it takes more space to sort.

[Matthias Muth]

Great idea, and great explanation!
Thanks for the inspiration!