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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
#
# know-your-place.pl
#
# TASK #2 › Search Insert Position
# Submitted by: Mohammad S Anwar
# You are given a sorted array of distinct integers @N and a target $N.
#
# Write a script to return the index of the given target if found
# otherwise place the target in the sorted array and return the index.
#
# Example 1:
# Input: @N = (1, 2, 3, 4) and $N = 3
# Output: 2 since the target 3 is in the array at the index 2.
#
# Example 2:
# Input: @N = (1, 3, 5, 7) and $N = 6
# Output: 3 since the target 6 is missing and should be placed at the index 3.
#
# Example 3:
# Input: @N = (12, 14, 16, 18) and $N = 10
# Output: 0 since the target 10 is missing and should be placed at the index 0.
#
# Example 4:
# Input: @N = (11, 13, 15, 17) and $N = 19
# Output: 4 since the target 19 is missing and should be placed at the index 4.
#
#
# method:
# We could take a naive approach — a brute force assault of the
# citadel, boldly running the gauntlet through the front door up to
# the insert point, but we can do better. We can be sneaky and
# improve our idea of where we're going with every step we take. If
# we by start in the middle and successively subdivide the remaining
# range, we can home in on the correct placement.
# This method is a version of a binary search: we start off knowing
# that the correct location, whatever that may be, lies within the
# bounds of the array after the new element has been added. I mean,
# it might be tautologically obvious that after the element has been
# added, it will be held at some position within the array, but you
# have to start somewhere. We know, thus, before we start that the
# lower bound for the correct placement is 0, and the upper bound is
# the length of starting array plus one, for the new element. The
# known range is quite broad at this point, but through a series of
# actions we can refine it until there is only one position left,
# which is the correct place to insert the new element.
#
# We start by looking to add the element at the half-way point. At
# every trial, first we see whether the index we're examining is the
# value we're inserting. If it is, we've found the placement and
# we're done.
#
# In the more-likely chance it's not equal, the value will either
# greater than or less than that at the position. Again, stands to
# reason. And with that calculation we've learned some new
# information: for example, if the value is greater, than the
# correct location cannot be less than that index. We can now adjust
# our boundaries; the lower limit can be moved upwards to our mark.
# We can also reset it to be one greater than the checked postion,
# as we know it doesn't lie there either. Likewise, if the value is
# less, we move the pointer for the upper bound to be the index one
# less than the one tried.
#
# We've now constricted the known range for the correct insert index
# by one-half. Not bad. We can continue to do this repeatedly, at
# each pass redefining the available range for the result, until
# either we land on an existing element with the value or the the
# value at the index one below is less and the value at the index is
# greater. If this is the case then we have located to correctly
# sorted location for the new element.
#
# Because the directives say to insert the element into the list,
# we'll take the list in as an array reference, then apply the
# splice to the referenced list once we've found the insert point.
# If the element is already there we'll of course leave things be.
# In any case the list is altered in-place and the position of the
# new element is returned
#
#
# © 2021 colin crain
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
use warnings;
use strict;
use feature ":5.32";
sub insert {
my ($num, $arr) = @_;
$num > $arr->[-1] and do { push $arr->@*, $num; return $#$arr };
$num < $arr->[0] and do { unshift $arr->@*, $num; return 0 };
my $lower = 0;
my $upper = $#$arr;
while ( $lower <= $upper ) {
my $pos = int( ($lower+$upper)/2 ); ## midpoint
return $pos if $arr->[$pos] == $num;
if ($arr->[$pos-1] < $num < $arr->[$pos]) {
splice( $arr->@*, $pos, 0, $num );
return $pos;
}
$arr->[$pos] > $num ? ($upper = $pos-1) ## restrict the range
: ($lower = $pos+1);
}
}
use Test::More;
is insert( 3, [1, 2, 3, 4] ), 2, 'ex-1, exists already';
is insert( 6, [1, 3, 5, 7] ), 3, 'ex-2, insert into middle';
is insert( 10, [12, 14, 16, 18] ), 0, 'ex-3, less than first';
is insert( 19, [11, 13, 15, 17] ), 4, 'ex-4, more than last';
for my $n (1..13) {
$n = 500 - 37*$n;
is insert( $n, [1..500] ), $n-1, "long list: target -> $n";
}
is insert( 1, [2, 4, 6, 8] ), 0, 'insert into idx 0';
is insert( 3, [2, 4, 6, 8] ), 1, 'insert into idx 1';
is insert( 5, [2, 4, 6, 8] ), 2, 'insert into idx 2';
is insert( 7, [2, 4, 6, 8] ), 3, 'insert into idx 3';
is insert( 9, [2, 4, 6, 8] ), 4, 'insert into idx 4';
is insert( 2, [2, 4, 6, 8] ), 0, 'match idx 0';
is insert( 4, [2, 4, 6, 8] ), 1, 'match idx 1';
is insert( 6, [2, 4, 6, 8] ), 2, 'match idx 2';
is insert( 8, [2, 4, 6, 8] ), 3, 'match idx 3';
done_testing();
|
