Task — Target index

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 same as the given target element.

Examples

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 $k[2] = 2

Example 2
Input: @ints = (1, 2, 4, 3, 5), $k = 6
Output: ()

No element in the given array matching the given target.

Example 3
Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4
Output: (4)

Sorted array: (1, 2, 2, 3, 4, 5)
Target index: (4) as $ints[4] = 4

Analysis

The obvious solution is to sort @ints, and then there is a one-line answer:
$output .=
 $ints[$_] == $k ? qq[$_, ] : '' for 0 .. @ints - 1;

- but that's not what I've submitted.

Instead, and because a sort is expensive if @ints is very large - say a million integers - a better algorithm is to pass once through the unsorted array:

• counting the number of integers less than $k - call that $n, and
• counting the number of instances of $k - call that $m.

The solution is then simply $n .. ($n + $m - 1).

I tried that with a million integers and the answer came back in a few seconds.

Try it 

Script

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-04-01
use utf8;     # Week 263 - task 1 - Target index
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my (@ints, $j);

target_index([1, 5, 3, 2, 4, 2], 2);
target_index([1, 2, 4, 3, 5], 6);
target_index([5, 3, 2, 4, 2, 1], 4);

# bigger example
for $j (0 .. 500) {
    push @ints, int(rand(30) + 1);
}
target_index(\@ints, 15);

sub target_index {
    
    my (@ints, $int, $k, $m, $n, $output);
    
    # initialise
    @ints = @{$_[0]};
    $k = $_[1];
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . qq[), \$k = $k];
        
    # count integers less than $k and equal to $k
    $n = $m = 0;
    for $int (@ints) {
        $n ++ if $int < $k;
        $m ++ if $int == $k;
    }
    
    # show results  
    $output = '';
    $output .= qq[$_, ] for $n .. ($n + $m - 1);
    say qq[Output: (] . substr($output, 0, -2) . ')';
}

Output

Input:  @ints = (1, 5, 3, 2, 4, 2), $k = 2
Output: (1, 2)

Input:  @ints = (1, 2, 4, 3, 5), $k = 6
Output: ()

Input:  @ints = (5, 3, 2, 4, 2, 1), $k = 4
Output: (4)

Input:  @ints = (500 random numbers in 0 .. 29), $k = 15
Output: (252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265)