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
|
#!/usr/bin/gawk
# Challenge 098
#
# 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.
# print contents of array (nums, nums_size)
function print_array() {
sep = "";
printf "("
for (i=0; i<nums_size; i++) {
printf sep nums[i];
sep = ", ";
}
print ")";
}
# insert an element in (nums, nums_size), shifting all other positions up
function insert(p, n) {
nums_size++;
for (i=nums_size-1; i>p; i--)
nums[i] = nums[i-1];
nums[p] = n;
}
# use bisect method to search for position
function search_insert(n) {
if (nums_size == 0) { # input empty
nums[nums_size++] = n;
return 0;
}
else if (n < nums[0]) { # before first
insert(0, n);
return 0;
}
else if (n > nums[nums_size-1]) {# after last
nums[nums_size++] = n;
return nums_size-1;
}
else { # bisect
bot = 0; top = nums_size;
mid = int((top + bot) / 2);
while (bot+1 < top) {
if (n == nums[mid])
return mid;
else if (n < nums[mid])
top = mid;
else
bot = mid;
mid = int((top + bot) / 2)
}
# not found, insert at mid+1
insert(mid+1, n);
return mid+1;
}
}
BEGIN {
n = ARGV[1];
nums_size = 0; # nums[] size
for (i = 2; i < ARGC; i++) {
nums[nums_size++] = ARGV[i];
}
p = search_insert(n);
print p;
print_array();
exit 0;
}
|
