Searching for a missing number in a sequence of numbers

Question

So I have a file that has whole bunch of information and each "block" of information has it's own unique identifier, which is shown as:

"index": number

after using the following command in linux:

$ cat file | grep index

I get this result:

"index": 1
"index": 2
"index": 3
...
"index": 10001

In between them is a whole range of numbers in sequential format.

Somewhere in there, there is a missing number and I am trying to figure out which number that is.

I have tried several things, but none have worked. Is there another command I can add on to it or is there a better way to search for the missing index number?

Answer 1

You can use diff command to get the differences between your file and the sequence of number from N to M. The awk command is used to parse the text and get only the numbers:

diff --side-by-side --suppress-common-lines  <(awk '{print $2}' file.txt) <(seq 1 10001) | awk '{print $2}'

The code above compare the numbers of your file with the sequence from 1 to 10001.

For a more functional way to implement this you can detect the last number of your file (10001) and assign it to a variable:

max=$(tail -1 file.txt | awk '{print $2}')
diff --side-by-side --suppress-common-lines  <(awk '{print $2}' file.txt) <(seq 1 $max) | awk '{print $2}'

For example, having this:

file.txt:

"index": 1
"index": 5
"index": 8
"index": 9
"index": 10
"index": 12
"index": 13
"index": 15

max=$(tail -1 file.txt | awk '{print $2}')
diff --side-by-side --suppress-common-lines  <(awk '{print $2}' file.txt) <(seq 1 $max) | awk '{print $2}'

Output:

2
3
4
6
7
11
14

By the way, if you want to print the missing values in this format: "index": the_missing_number you could change the last awk print statement like this:

diff --side-by-side --suppress-common-lines  <(awk '{print $2}' file.txt) <(seq 1 $max) | awk '{print "\"index\": "$2}'

Answer 2

Two important assumptions about the file that contains the index labels and integers, from your example:

"index": 1
"index": 2
"index": 3
...
"index": 10001

The assumptions are:

1. When read from the first line to the last, the index integers are in ascending order.
2. One or more spaces or tabs separate the "index": label from the index integer.

As long as both are true, this small loop in bash can output missing numbers (but read my caveat after the code). The file with the index labels and integers is named indexes.txt:

cur_idx=0
last_idx=0
while read label cur_idx; do
  (( last_idx != ( cur_idx - 1 ))) && echo $(( cur_idx - 1 ))
  last_idx=${cur_idx}
done < indexes.txt

The loop remembers the last index seen, and after it reads a new index line, it compares the current (new) index [minus 1] with the last index. When they're not equal, an index was skipped and it prints the skipped index.

Caveat:

If there are two or more consecutive missing indexes, this loop will only print out the first missing one. It won't print all of them.
I.e., if you have:

"index": 21
"index": 24

(missing 22 and 23), the loop will only print 22. However, that will let you look at the indexes.txt file after 21 and see how many numbers were skipped. I get the impression from your question that there are only one or two missing indexes, so this shouldn't hinder you.

Answer 3

You can do this with a simple grep/awk statement. The first line matching index that does not have the same number as the awk line number (NR) then print the line number and exit.

grep index file | awk -F: '{ if (NR != $2 ) {print "missing " NR; exit;} }'

Answer 4

Assuming that the input is a JSON file consisting of a top-level array of object, each with some index key, like so:

[
  {
    "index": 2
  },
  {
    "index": 3
  },
  {
    "index": 4
  },
  {
    "index": 6
  },
  {
    "index": 7
  },
  {
    "index": 10
  }
]

We may then use the JSON processor jq to pick out the index values of the first and last element of the array, create a set of numbers that span that range (apart from the actual first and last values), and then output the ones of those that do not correspond to an existing index value:

$ jq '[.[].index] as $i | ($i|range(first+1;last)) | select( IN($i[]) | not )' file
5
8
9

If the input is unordered, you will want to change range(first+1;last) to range(min+1;max).

Answer 5

Using Raku (formerly known as Perl_6)

~$ raku -e 'my @a; for lines() {@a.push: $/.Int if .match(/<?after \"index\"\: \s > \d+ /) };  \
            put ((1..10) (-) @a.Set).keys.sort;'  index.txt
#OR
~$ raku -e 'my @a; for lines() {@a.push: $0.Int if .match(/<?after &quot;index&quot;: \s > (\d+) /) };  

            put ((1..10) (-) @a.Set).keys.sort;'  index.txt

Raku is a programming language in the Perl-family. It was released in 2015 as Perl_6, and renamed Raku in 2019. Consequently, you'll find many "Perl-isms" in Raku.

One interesting feature of Raku is Set semantics. Unicode as well as ASCII operators are available. In the code above, ASCII (-) stands for Set difference (non-symmetric). You can also use Unicode:

∖
SET MINUS
Unicode: U+2216, UTF-8: E2 88 96

Sample Input (note max value is 100):

"index": 1
"index": 2
"index": 3
"index": 5
"index": 100

Sample Output (both code examples):

4 6 7 8 9 10

Caveat: It can be easy to confuse symmetric and non-symmetric Set operations. For example, with the code above if you reverse the order of sets and try the ASCII (^) or Unicode ⊖ symmetric Set difference operator instead, you'll see a big difference (using 1..99 as the test range):

~$ cat index.txt | perl6 -e 'my @a = do for lines() {$/.Int if .match(/<?after \"index\"\: \s > \d+ /) }; put (@a.Set (-) (1..99)).keys.sort;'
100
~$ cat index.txt | perl6 -e 'my @a = do for lines() {$/.Int if .match(/<?after \"index\"\: \s > \d+ /) }; put (@a.Set (^) (1..99)).keys.sort;'
4 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

https://docs.raku.org/language/setbagmix
https://raku.org

Answer 6

You should be able to do this purely in awk:

awk '$1=="\"index\":"{if (last && $2!=(last+1)) {printf "Missing index: %d\n",last+1;}; last=$2}' input.txt

This will only process files whose first "word" is "index":. The second "word" of that line ($2) will be treated as the ID.

• The ID value of the previous index line is stored in a variable last. The variable is empty at the beginning.
• If there was already a "previous" index line (last evaluates to non-empty), and the current index value is different from the last index plus one, the missing value is printed as "Missing index".
• In any case, the last value is updated to the index value of the current line.
• If, as you write, there will only be one single missing index value in the entire file, you can skip processing the remaining file by adding an exit command after the printf() call.

This allows for the indices starting at a value other than 1 (which however must still be positive), but assumes that there can only be single missing values. If more than one consecutive indices can be missing, the following adaptation will print ranges of missing indices:

awk '$1=="\"index\":"{if (last && $2!=(last+1)) {for (t=last+1;t<$2;t++) printf "Missing index: %d\n",t}; last=$2}' input.txt

This is accomplished by a for loop iterating from last+1 (the first missing index) to one less than the current line index.

Answer 7

Here's a one-liner using just jot and diff, without any unnecessary parsing or awk steps:

$ diff --side-by-side --suppress-common-lines <(jot -w '"index": %d' 10001) file

This method simply generates a known-good output sample, and compares file to the known-good sample.

Test:

$ jot -w '"index": %d' 6665 > testfile
$ jot -w '"index": %d' - 6667 10001 >> testfile
$ diff --side-by-side --suppress-common-lines <(jot -w '"index": %d' 10001) testfile
"index": 6666

Answer 8

Will detect any gaps and single absences in consecutive, ascending numbering.

awk '$1 ~ /^"index":$/ {while(++i<$2)print $1, i}' file

Answer 9

A loop? Something like

for i in {1..10001}
do
  if ! grep "\"index\": $i" then
      echo Missing index $i
  fi
done