blob: abe58c903d00169d58cd19aefcffaefd48cf2367 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#!/opt/perl/bin/perl
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
#
# See ../README.md
#
#
# Run as: perl ch-2.pl < input-file
#
# Each line is assumed to be a white space separated list of
# numbers. The first number is the target number (`$N`), the rest of
# the numbers is the array (`@N`).
#
# Now, we could implement a binary search to find the target in
# O (log N) time, but why bother? We need to read the array, which
# means we're already spending linear time; furthermore, we have to
# insert element if not found -- which is a worst case linear time
# operation anyway. So, we just do a linear scan.
#
# Note that we insert $N into @N by adding it to the end, and then
# sorting -- which is linear in Perl (as the list (@N, $N) is nearly
# sorted). We then use a goto to go back to the search; this is
# guaranteed to succeed.
#
INPUT: while (<>) {
chomp;
my ($N, @N) = split ' ';
SEARCH:
for my $i (keys @N) {
if ($N == $N [$i]) {
say $i;
next INPUT;
}
}
#
# Not found. Insert by adding to the end and sorting.
#
@N = sort {$a <=> $b} @N, $N;
#
# Now, do the search again -- this time, it will succeed.
#
goto SEARCH;
}
__END__
|
